如何在三角形数字中找到最大路径和

Question

我正在尝试编写一个程序来找到三角形的最大路径和。路径总和是从顶部到底部出现在路径上的数字之和，因此在每条路径上，下一个数字直接位于下方或下方，并且位于右侧，如下所示：

1
12
123
1234

我在互联网上看到了一个解决这个问题的算法，但输出仍然是数组索引[0][0]的原始值。

这是我用C语言编写的代码：

#include<stdio.h>
int main(){
    int rows,testcases;
    scanf("%d",&testcases);
    scanf("%d",&rows);
    int a[rows][rows];
    while(testcases--){
        for(int i=0;i<rows;i++){
        for(int j=0;j<i+1;j++)
            scanf("%d",&a[i][j]);
        }

        for(int i=rows;i>1;i--){
            for(int j=0;j<i-1;j++){
                if(a[i][j]>a[i][j+1]){
                    a[i-1][j]=a[i-1][j]+a[i][j];
                }
                else{
                    a[i-1][j]=a[i-1][j]+a[i][j+1];
                }
            }
       }

        printf("The Largest Path Sum = %d",a[0][0]);
    }
    return(0);
}

我期望数组索引0 =最大的总和。实际结果是原始值

Answer 1

你有一个自下而上的动态编程解决方案。您的循环条件不正确。迭代从rows - 1到1的外环和从0到i-1的内环。

然后解决方案如下所示：

for(int i = rows - 1;i > 0;i--){
  for(int j = 0;j < i;j++){
    if(a[i][j] > a[i][j+1]){
      a[i-1][j] = a[i-1][j] + a[i][j];
    }
    else {
      a[i-1][j] = a[i-1][j] + a[i][j+1];
    }
  }
}