Как найти наибольшую сумму пути в треугольнике чисел

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