Baekjoon - Integer Triangle

Baekjoon : Integer Triangle

Description

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5 (Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

Constraints

1. Each step can go either diagonally down to the left or diagonally down to the right
2. The number of rows in the triangle is ≥ 1 but ≤ 500.
3. The numbers in the triangle, all integers, are between 0 and 9999 (inclusive).

Examples

Input

5 // # of Lines in the Triangle
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Output

30
// 7 -> 3 -> 8 -> 7 -> 5

Approach

When the problem asks for highest / lowest value, dynamic programming can be used to crack the problem

Recurrence Relation

Assuming two arrays - tri[i][j] & dp[i][j]

• if (j = 1) => dp[i][j] = dp[i-1][j] + tri[i][j]
• if (j = i) => dp[i][j] = dp[i-1][j-1] + tri[i][j]
• else => dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j];

Solution (C++)

#include <iostream>
using namespace std;

int N, answer = -1;
int tri[501][501];
int dp[501][501];

int max(int i, int j)
{
    return i > j ? i : j;
}

int main()
{
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            cin >> tri[i][j];
        }
    }

    dp[1][1] = tri[1][1];

    for (int i = 2; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1)
            {
                dp[i][j] = dp[i-1][j] + tri[i][j];
            }
            else if (j == i)
            {
                dp[i][j] = dp[i-1][j-1] + tri[i][j];
            }
            else
            {
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j];
            }
        }
    }

    for (int i = 1; i <= N; i++)
    {
        if (dp[N][i] > answer)
        {
            answer = dp[N][i];
        } 
    }

    cout << answer;

    return 0;
}