记忆是否适用于所有DP问题

Question

我正在解决这个著名的DP问题(ROD切割(问题链接

我理解社论中给出的方法，但我想出了自己的递归解决方案。。

这确实有效，但时间限制超过了，所以当我尝试记忆相同的内容时，我得到了不同的答案

代码：

#include <bits/stdc++.h>
using namespace std;
// Approach 1:
// Recursion
int helper1(vector<int> &price, int size, int index, int profit)
{
if (size == 0)
return profit;
if (size < 0 or index == price.size())
return INT_MIN;
return max(helper1(price, size - (index + 1), index, profit + price[index]),
helper1(price, size, index + 1, profit));
}
int cutRod1(vector<int> &price)
{
int n = price.size();
return helper1(price, n, 0, 0);
}
// Approach 2:
// Recursion + Memoization
int helper2(vector<int> &price, int size, int index, int profit, vector<vector<int>> &dp)
{
if (size == 0)
return profit;
if (size < 0 or index == price.size())
return INT_MIN;
if (dp[index][size] != -1)
return dp[index][size];
return dp[index][size] = max(helper2(price, size - (index + 1), index, profit + price[index], dp),
helper2(price, size, index + 1, profit, dp));
}
int cutRod2(vector<int> &price)
{
int n = price.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
return helper2(price, n, 0, 0, dp);
}
void solve()
{
vector<int> price{3, 9, 13, 12, 8, 12, 8, 8, 3, 10, 13};
cout << cutRod1(price) << endl;
cout << cutRod2(price) << endl;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t{1};
// cin >> t;
while (t--)
solve();
return 0;
}

递归解决方案的结果：49(正确(

记忆化解决方案的结果：48(错误(

我的方法背后的直觉：

这是一个无界背包问题，我们有两个选择：

1. 在指数的位置切入并停留在那里(用于在同一位置进一步切入(
2. 不在指数的位置进行切割，移动到下一个指数(指数+1(

有人能帮我找出记忆版本不起作用的原因吗

Answer 1

您需要在内存查找中包含profit。在某种程度上，您使用相同的(大小、索引(对调用helper，但传入的利润值不同。

Answer 2

这是一个具有记忆功能的解决方案。来源包含完整的解释。源

#include <iostream>
#include<algorithm> // To use the built in max function
using namespace std;
int main() {
// Suppose that we have a rod of length 5, and an array containing the 
// length(1,2,3 and 4 ) and price(2,5,7 and 8 ) of the pieces.
int price[] = {2,5,7,8};
int n = 5;
// Declaring a 2D array, T
int T[n-1][n+1];
// Initializing the array to all zeros
for(int i=0; i < n-1; i++)
{
for(int j=0; j < n+1; j++ )
{
T[i][j] = 0;
}
}
for(int i=0; i < n-1; i++)
{
for(int j=0; j < n+1; j++ )
{
// First column => 0 length of rod => 0 profit
if(j == 0) {
continue;
}
// First row => T[i-1][j] doesn't exist so just pick the second value
else if(i == 0) {
T[i][j] = price[i] + T[i][j-i-1];
}
// where j <= i => T[i][j-i-1] doesn't exist so just pick the first value
else if(j-i-1 < 0) {
T[i][j] = T[i-1][j];
}
// using the whole expression
else {
T[i][j] = std::max(T[i-1][j], (price[i] + T[i][j-i-1]));
}
}
}
// Answer in the extreme bottom right cell
cout << "Maximum profit is " << T[n-2][n] << endl;

return 0;
}