120. 三角形最小路径和
一道非常经典且历史悠久的动态规划题


解法：动态规划
用 dp[i][j] 表示从三角形顶部走到位置 (i, j) 的最小路径和。这里的位置 (i, j) 指的是三角形中第 i 行第 j 列（均从 0 开始编号）的位置。
由于每一步只能移动到下一行「相邻的节点」上，因此要想走到位置 (i, j)，上一步就只能在位置 (i-1, j-1) 或者位置 (i - 1, j) 中选择一个路径和较小的来进行转移，状态转移方程为：

dp[i][j]=min(dp[i−1][j−1], dp[i−1][j]) + triangle[i][j]

注意第 i 行有 i+1 个元素，它们对应的 j 的范围为 [0, i] 。当 j=0 或 j=i 时，上述状态转移方程中有一些项是没有意义的。
例如当 j=0 时，dp[i−1][j−1] 没有意义，因此状态转移方程为：

dp[i][0] = dp[i-1][0] + triangle[i][0]

即当在第 i 行的最左侧时，只能从第 i−1 行的最左侧移动过来。

当 j=i 时，dp[i−1][j] 没有意义，因此状态转移方程为：

dp[i][i] = dp[i-1][i-1] + triangle[i][i]

即当我们在第 i 行的最右侧时，我们只能从第 i−1 行的最右侧移动过来。

最终的答案即为 dp[n−1][0] 到 dp[n−1][n−1] 中的最小值，其中 n 是三角形的行数。C++中Vector求最大值最小值

边界条件为：dp[0][0]=triangle[0][0]

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<vector<int>> dp(n,vector<int>(n));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<n;i++){
            dp[i][0]=dp[i-1][0]+triangle[i][0];
            for(int j=1;j<i;j++){
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
            }
            dp[i][i]=dp[i-1][i-1]+triangle[i][i];
        }
        int ans=*min_element(dp[n-1].begin(),dp[n-1].end());
        return ans;
    }
};