记忆递归解决方案(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初始化为你将返回的值。