c - 如何找到数字三角形中的最大路径和

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];
    }
  }
}