7/14刷题

1.三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
思路：动态规划

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        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],dp[i-1][j-1])+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());//返回最后一行最差的
    }
};