Need Help Debugging Solution for a DP Problem

Need Help Debugging Solution for a DP Problem

Hello,

I have been trying to solve this problem from POJ 1163.

I figured out the two main base cases (the "left" and "right" side of the triangle), and then I solve the "inside" of the triangle by adding the max "parent" node.

With the given example input, I was able to get the expected answer (30). I tried it with a few other cases I made up, and I got the expected answer. However, the answer is wrong according to the judge.

I would really appreciate it if someone could explain where the error is in my solution. Thank you.

Attempted Solution:

#include <iostream>
#include <algorithm>

#define ll long long

using namespace std;

int main() {
    // Input 
    int n;
    cin >> n;
    int dp[1000][1000];
    int p = 1;
        
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INT_MIN;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            cin >> dp[i][j];
        }
        p++;
    }
    // Base Case #1 - The "left" side of the triangle
    for (int i = 1; i < n; i++) {
        dp[i][0] += dp[i-1][0]; 
    }
    // Base Case #1 - The "right" side of the triangle
    for (int i = 1; i < n; i++) {
        dp[i][i] += dp[i-1][i-1];
    }
    // Solving the "inside" of the triangle by adding the max of the 3 possible "parent" nodes
    int cn = 2;
    for (int i = 2; i < n; i++) {
        for (int j = 1; j < cn; j++) {
            dp[i][j] += max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]);
        }
        cn++;
    }
    // The bottom of the triangle will have the largest sum, so iterating over that and finding the largest integer will give us the answer

    ll ans = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (dp[n-1][i] > ans) ans = dp[n-1][i];
    }
    cout << ans << '\n';
    return 0;
}