CODEWITHSUNDEEP
cdynamic-programming
ahmed galal
ahmed galal

Reputation: 3

How to find the largest path sum in a triangle of numbers

I'm trying to write a program to find the largest path sum of a triangle. A path sum is sum of numbers that appear on the paths starting from the top towards the base, so that on each path the next number is located directly below or below-and-one-place-to-the-right like below:

1
12
123
1234

I saw an algorithm on the internet that solves this problem, but the output remains as the original value of array index [0][0].

Here's my code in C language:

#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);
}

I expected that array index 0 = the largest sum. The actual result is the original value

Upvotes: 0

Views: 667

Answers (1)

Mukul Gupta
Mukul Gupta

Reputation: 2425

You have a bottom up dynamic programming solution. Your loop conditions are incorrect. Iterate the outer loop from rows - 1 to 1 and inner loop from 0 to i-1.

The solution then looks as follows:

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

Upvotes: 1

Related Questions