保留递归解决方案（DP）

Question

我已针对问题https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee编写了此递归我想知道我们如何记住这个解决方案（使用dp数组）。还是我们必须以特定的方式编写递归来记住它？

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等于solve（i）。然后，在函数内部，可以通过引用每个调用来传递此数组。您可以在函数测试中添加if / else结构，以检查是否在数组中定义了获得的输入，如果是，则返回arr [input]；否则，请通过正常函数运行，除非在返回之前，您要初始化arr [input]到您将返回的值。