如何将此递归函数转换为基于 dp 的解决方案？

Question

这是递归函数

def integerPartition(m, n):
    if(n==0):
        return 0
    if(m ==0):
        return 1
    if(m<0):
        return 0

    return integerPartition(m,n-1) + integerPartition(m-n,n)

这就是我在 C++ 中所做的

        // n -> no. of persons
        // m -> amount of money to be distributed
        // dp table of order (n+1)*(m+1) 
        long long int dp[n+1][m+1] ;
        //initializing values to 0
        for(i = 0; i<=n ; i++)
            for(j = 0; j<= m ; j++)
                dp[i][j] = 0;

        Print(n,m,dp);
        cout << "\n";
        //Case 1 - if there is no persons i.e n = 0 answer will be 0
        //Case 2 - if there is no money i.e. m = 0 there is only 1 way answer will be 1
        for ( i = 1; i<= n ; i++ )
            dp[i][0] = 1;
            dp[i][i] = 1;

        Print(n,m,dp);

        for ( i = 1; i<= n ; i++){
            for ( j = 1; j<= m ; j++){
                dp[i][j] = dp[i][j-1] ;

                if(i>=j){
                    dp[i][j] += dp[i-j][j];
                }
                // else if(i==j){
                //     dp[i][j] += 1;
                // }
            }
    }

但是我得到的答案与递归答案不匹配我不明白我错过了什么如果有人可以帮助我更正我将不胜感激因为我刚刚开始动态编程我真的想不通

Answer 1

不确定这个技术上是DP，但如果你的目标是获得DP的好处，记忆可能会更好方法。

这个想法由两部分组成：

在每次调用 integerPartition 的开始时，在 table 中查找（您的 dp 会做得很好）以查看该计算是否已经已经完成，如果已经完成，只需 return 存储在 table.
就在 integerPartition 到 return 值的任何点之前，将其存储在 table.

请注意，这意味着您无需尝试 "pivot" 原始代码 -- 它的运行方式与最初相同，因此几乎可以保证您获得相同的结果，但没有那么多不必要的重新计算（在额外存储的代码）。

Answer 2

所以，你的代码注释的基础，根据你的递归代码，我假设当 n > 0 且 m = 0 时你只想要 1，但在 dp 代码中，你互换了它们，即我达到 n，j 达到 m 所以更新你的代码，试着找出错误


        // n -> no. of persons
        // m -> amount of money to be distributed
        // dp table of order (n+1)*(m+1) 
        long long int dp[n+1][m+1] ;
        //initializing values to 0
        for(i = 0; i<=n ; i++)
            for(j = 0; j<= m ; j++)
                dp[i][j] = 0;

        Print(n,m,dp);
        cout << "\n";
        //Case 1 - if there is no persons i.e n = 0 answer will be 0
        //Case 2 - if there is no money i.e. m = 0 there is only 1 way answer will be 1

        for ( i = 1; i<= n; i++){
            dp[i][0] = 0;
        }

        for(int j = 1; j <= m; j++){
            dp[0][j] = 1;
        }

        Print(n,m,dp);

        for ( i = 1; i<= n ; i++){
            for ( j = 1; j<= m ; j++){
                dp[i][j] = dp[i][j-1] ;

                if(i>=j){
                    dp[i][j] += dp[i-j][j];
                }
                // else if(i==j){
                //     dp[i][j] += 1;
                // }
            }
    }

Answer 3

一些问题：

您似乎在 for 循环中使用了非局部变量。这是一种不好的做法，会导致难以调试的错误。反而做 for (int i = 1; ...等
dp[i][i] = 1; 不是 for 循环的一部分。如果您只将 i 定义为 for 循环的局部变量，您就会检测到这一点。最好始终对 for 循环（还有 if、else、...等）的主体使用大括号，即使您只有一个正文中的声明。
dp[i][i] = 1; 也是一个错误的分配：integerPartition(i, i) 总是 returns 1 是不正确的。它恰好是正确的对于 i 的小值，但当 i 大于 3 时则不然。例如，integerPartition(4, 4) 应该 return 5。只需删除这一行。
在最后的嵌套 for 循环中，您混淆了 dp 数组中的 row/column。请注意，您为 n 保留了第一个维度，为 m 保留了第二个维度，因此与参数顺序相反。这很好，但是您不要坚持这个 for 循环中的那个决定。而不是 dp[i][j-1] 你应该写 dp[i-1][j] 而不是 dp[i-j][j] 你应该写写成dp[i][j-i]。因此 if 条件应相应调整。
您的版本中没有 return 语句，但也许您只是忘记将其包含在问题中。它应该是 return dp[n][m];

这是更正后的代码：

long long int dp[n+1][m+1];

for(int i = 0; i <=n; i++) {
    for(int j = 0; j <= m; j++) {
        dp[i][j] = 0;
    }
}

for (int i = 1; i <= n; i++) {
    dp[i][0] = 1;
}

for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m ; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= i) {
            dp[i][j] += dp[i][j-i];
        }
    }
}

return dp[n][m];

如何将此递归函数转换为基于 dp 的解决方案？

How to convert this recursive function to a dp based solution?

algorithm

implementation

dynamic