Shown below is a number triangle. I need a program to find a path starting from the top and ending at the bottom. The numbers in the path should add up, and I want to find the largest number. A few rules :
- Every step can go straight down or right down (diagonal);
- The number of triangle rows is less than or equal to 100;
- The numbers in the triangle rows are 0, 1, ..., 99;
The Triangle of Numbers below is an example, and the code should output 30. (the path should be 7->3->8->7->5 and the sum is 30)
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
The input is an integer, the height of the triangle, and the triangle itself, and the output should be one number, the largest path. The input for the example shown above should be 5, and then the rest of the triangle. This may seem like kind of an easy and dumb question but I am pretty new to programming and could not find any answers online.
#include <iostream>
using namespace std;
int main() {
int rows;
cin >> rows;
int triangle[rows][rows];
for (int i = 0; i < rows; ++i) {
for (int j = 0; j <= i; ++j) {
cin >> triangle[i][j];
}
}
for (int i = rows-2; i >= 0; i--) {
for (int j = 0; j < i + 1; j++) {
int down = triangle[i][j] + triangle[i+1][j];
int right = triangle[i][j] + triangle[i+1][j+1];
if (down > right) {
triangle[i][j] = down;
} else {
triangle[i][j] = right;
}
}
}
cout << triangle[0][0];
return 0;
}
this is my current code to find the largest path but it doesn't work for some reason.