计算 C 中矩阵的最大路径成本

Question

我正在学习 c 并遇到最大成本路径问题，其中

规则：

1. 矩阵为 nxn 大小

2. 从单元格（最左下角的单元格）开始，想要走到最上面 步骤序列中最右边的单元格。在每一步中，您可以向右或向上 您当前的位置。

我尝试使用动态编程来解决，这是我编写的函数

computecost(int *utr,int n)//utr is the input matrix 
{
 int *str;
 int i,j;
 str=(int *)malloc(n*n*sizeof(int));
 for(j=0;j<n;j++)//intialization of bottom row
 {
      str[n*(n-1)+j]=utr[n*(n-1)+j];
 }
 for(i=n-2;i>=0;i--)
 {
     for(j=0;j<n;j++)
     {
         str[n*i+j]=utr[n*i+j]+max(str[n*(i+1)+j],str[n*(i+1)+(j+1)]);   
     }
 }
 
printf("%d",str[n*0+0]);
 
 return 0;
}

，这是输入，

for(i=0;i<n;i++)
 {
     for(j=0;j<n;j++)
     {
         scanf("%d",&str[n*i+j]);
     }
 }  

但是 对于矩阵 5 x5，

1   4   8   2   9 

32  67  18  42  1 

4   86  12  7   1 

8   4   12  17  44

1   43  11  45  2 

所需的输出是 272，但我得到 211。

我的案例的输出矩阵

  1   43  11  45  2
  51  47  57  62  46
  55  143  74  69  47
  175  210  92  111  52
  211  214  119  113  64

有人可以帮助我吗？

Answer 1

你距离成功已经不远了。
实际上，您没有正确初始化底行。
而且，迭代计算时出现了一点错误。

这是更正后的代码。
正如评论中所述，通过避免使用新数组，只需更新输入数组，可以进一步简化它。

#include <stdio.h>
#include <stdlib.h>

int max (int a, int b) {
    return (a > b) ? a : b;
}

int computecost(int *utr,int n) {   //utr is the input matrix 
    int *str;
    str = malloc (n*n*sizeof(int));
    str[n*n - 1] = utr[n*n - 1];
    for (int j = n-2; j >= 0; j--) {    //intialization of bottom row {
        str[n*(n-1)+j] = utr[n*(n-1)+j] + str[n*(n-1)+j+1];       // corrected
    }
    for (int i=n-2; i>=0; i--) {
        str[n*i+n-1] = utr[n*i+n-1] + str[n*(i+1)+n-1];
        for(int j = n-2; j >= 0; j--) {
           str[n*i+j] = utr[n*i+j] + max(str[n*(i+1)+j],str[n*i + j+1]); // corrected
        }
    }
    int cost = str[0];
    free (str);
    return cost;
}

int main() {
    int A[25] = {
        1,43,11,45,2,
        8,4,12,17,44,
        4,86,12,7,1,
        32,67,18,42,1,
        1,4,8,2,9
    };
    int ans = computecost (A, 5);
    printf ("%d\n", ans);
    return 0;
}

Answer 2

您不需要为此进行动态编程，因为不存在重叠的子问题。只需使用简单的递归即可。

const int n = 5;
int mat[n][n] = {
    {1,4,8,2,9},
    {32,67,18,42,1},
    {4,86,12,7,1},
    {8,4,12,17,44},
    {1,43,11,45,2}
}; // input matrix

int f(int x, int y, int sum){
    if(x == 0 && y == 4)
        return sum;

    int p = 0, q = 0;
    if(x - 1 >= 0)
        p = f(x-1, y, sum + mat[x-1][y]);
    if(y + 1 <= 4)
        q = f(x, y+1, sum+mat[x][y+1]);
    return max(p,q);
}

int main(){
    int maxSum = f(4,0, mat[4][0]);
    printf("%d\n", maxSum);
}