dp 捡水果

蒜头在玩一款游戏，他在一个山顶，现在他要下山，山上有许多水果，蒜头每下一个高度就可以捡起一个水果，并且获得水果的能量。山的形状如图所示：

3
1 2
6 2 3
3 5 4 1
1
2
3
4
这是一个高度为 4 的山，数字代表水果的能量。每次下一个高度，蒜头需要选择是往左下走，还是往右下走。例如：对于上图的情况，蒜头能获得的最大能量为，3+1+6+5=15。现在，蒜头希望你能帮他计算出下山能获得的最大能量。

输入格式
第一行输入一个 n，代表山的高度。（1

输出格式
输出一个数字，代表下山一共获得的最大能量，占一行。

样例输入
4
3
1 2
6 2 3
3 5 4 1
样例输出
15
————————————————

#include 

using namespace std;
long long a[1001][1001];
long long dp[1001][1001];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];      //简单输入
    for (int i = n; i >= 1; i--) //倒三角dp,上层数值为自己加上下一层最大的相邻数值(*注意是dp值),逐次回到(1,1)
        for (int j = 1; j <= i; j++)
        {
            if (i == n)
                dp[i][j] = a[i][j];
            else
                dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    cout << dp[1][1];
    return 0;
}