计算C中矩阵的最大路径开销

Question

我正在学习c，遇到了的最大成本路径问题

规则：

1. 矩阵是n x n大小的

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

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

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("%dn", maxSum);
}

Answer 2

你离成功不远了
在实践中，您没有正确初始化最下面的一行
此外，迭代计算中有一个小错误。

这是已更正的代码
正如在评论中所说，它可以通过避免使用新数组、简单地更新输入数组来进一步简化。

#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 ("%dn", ans);
return 0;
}