在递归重叠问题中应用DP记忆方法时出现错误

Question

我在递归Coin Change问题中应用了DP记忆方法。但我在使用记忆方法(自上而下的dp方法(来克服重叠问题时得到了错误的答案。

以下是递归解决方案(给出正确的结果(：

#include<stdio.h>
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
// If n is 0 then there is 1 solution
// (do not include any coin)
if(n==0)
return 1;
// If n is less than 0 then no
// solution exists
if (n < 0)
return 0;
// If there are no coins and n
// is greater than 0, then no
// solution exist
if (m <=0 && n >= 1)
return 0;

// count is sum of solutions (i)
// including S[m-1] (ii) excluding S[m-1]
return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
// Driver program to test above function
int main()
{
int i, j;
int arr[] = {1, 2, 3};
int m = sizeof(arr)/sizeof(arr[0]);
printf("%d ", count(arr, m, 4));
getchar();
return 0;
}

下面的代码是我应用的记忆方法(给出错误的答案(：

#include<stdio.h>
int dp[100];
// Returns the count of ways we can
// sum S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
// If n is 0 then there is 1 solution
// (do not include any coin)
if(n==0)
return 1;
// If n is less than 0 then no
// solution exists
if (n < 0)
return 0;
// If there are no coins and n
// is greater than 0, then no
// solution exist
if (m <=0 && n >= 1)
return 0;

//Memoization
if(dp[n]!=0)
return dp[n];

// count is sum of solutions (i)
// including S[m-1] (ii) excluding S[m-1]
return dp[n] = count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
// Driver program to test above function
int main()
{
int i, j;
int arr[] = {1, 2, 3};
int m = sizeof(arr)/sizeof(arr[0]);
int u;
dp[0]=1;
for(u=1;u<=99;u++)
dp[u] = 0;
printf("%d ", count(arr, m, 4));
getchar();
return 0;
}

我查了很多我做错的地方，但都查不出来。请帮忙找出错误。谢谢：(

Answer 1

您试图记忆n的特定值的结果，但却忘记了m。你需要一个二维备忘录表。有点像。

int dp[100][100];
int count(int S[], int m, int n) {
...
if (dp[n][m] != 0) return dp[n][m];
dp[n][m] = count(S, m - 1, n) + count(S, m, n - S[m - 1]);
return dp[n][m];
}
int main() {
...
int u;
for (int i = 0; i < 100; ++i) {
dp[0][i] = 1;
for (u = 1; u <= 99; u++) dp[u][i] = 0;
}
...
return 0;
}