徒弟的下山之路(DP版）

/*
想法是dp[i][j]存储的是i行j列为止最短的路径，那么由此可以进行递推，dp[i][j]肯定来自它的上，右上，右中的最小值(当然每行的第一个
和最后一个元素需要单独考虑),但是对每行仅作一次DP显然不够，因为这个最小值我们忽略了来自左边的值，因此做完之后我们需要再次DP，由此可以得出结果
*/
#include <iostream>
using namespace std;
typedef long long LL;
int arr[1002][1002]; // 读入地图信息
LL DP[1002][1002]; // DP数组
int N;
void solve();
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++)
            cin >> arr[i][j];  // 进行读入
    }
    solve();
}
void solve()
{
    for (int i = 1; i <= N; i++) { // 从第一行开始
        for (int j = i; j >= 1; j--) { // 从这一行的最后一个元素开始
            if (j == i) DP[i][j] = DP[i -1][j - 1] + arr[i][j];  // 考虑每行最后一个元素
            else if (j == 1) {
                DP[i][j] = min(DP[i - 1][j], DP[i][j + 1]) + arr[i][j]; // 考虑第一个元素
            }
            else {
                DP[i][j] = min(DP[i - 1][j], min(DP[i - 1][j - 1],DP[i][j + 1])) + arr[i][j]; // 考虑中间元素
            }
        }
        for (int h = 2; h <= i; h++)
            DP[i][h] = min(DP[i][h], DP[i][h - 1] + arr[i][h]); // 再次DP考虑左值
    }
    cout << DP[N][1] << endl;
}