Leetcode刷题笔记题解（C++）：120. 三角形最小路径和

思路：动态规划，去生成一个对应的当前节点的最小路径值，对应的关系如下所示

dp[0][0] = triangle[0][0]

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

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

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

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++){
                //(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];
            }
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];//每一行最右边为上一行最右边+当前值
        }
        return *min_element(dp[n-1].begin(),dp[n-1].end());
    }
};