запоминание рекурсивного решения (DP)

Question

Я написал эту рекурсию для задачи https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee Я хочу знать, как мы можем запоминать это решение (используя массив dp). или мы должны написать рекурсию определенным c способом, чтобы запомнить ее?

class Solution {
public:


    int solve(vector<int>& prices,int fee,int i,int profit,int buy,int sell)
    {
        if(i==prices.size())
        {
            if(buy==sell)
                return profit;
            else
                return 0;
        }

        int ans = 0;

        ans = max(ans,solve(prices,fee,i+1,profit,buy,sell));

        if(buy>sell)
        {
            ans = max(ans,solve(prices,fee,i+1,profit+prices[i]-fee,buy,sell+1));
        }
        else 
        {
            ans = max(ans,solve(prices,fee,i+1,profit-prices[i],buy+1,sell));
        }

        return ans;

    }

    int maxProfit(vector<int>& prices, int fee) {
        vector<int> diff;
        int sum = 0;
        sum = solve(prices,fee,0,0,0,0);

        return sum;
    }
};

Answer 1

Вы можете просто создать массив, где элемент i равен для решения (i). Затем внутри вашей функции вы можете передать этот массив по ссылке на каждый вызов. Вы добавляете структуру if / else в тестирование своей функции, если полученный вами вход был определен в массиве, если да, возвращайте arr [input], а если нет, выполняйте обычную функцию, за исключением того, что перед возвратом вы инициализируете arr [input] на значение вы вернетесь.