【leetcode刷题】T160-三角形最小路径和

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not len(triangle):
            return 0
        dp = [triangle[0][0]]
        for i in range(1, len(triangle)):
            for j in range(len(triangle[i])):
                if j == 0:
                    dp.insert(0, dp[0] + triangle[i][j])
                elif j == len(triangle[i]) - 1:
                    dp[j] += triangle[i][j]
                else:
                    dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
        return min(dp)

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size() == 0 || triangle[0].size() == 0)
            return 0;
        vector<int> dp;
        dp.push_back(triangle[0][0]);
        for(int i=1; i < triangle.size(); i++){
            // 首尾元素，直接+dp首尾元素
            // 其他元素，找到dp相邻元素最小值，再相加
            dp.insert(dp.begin(), dp[0] + triangle[i][0]);
            for(int j=1; j < triangle[i].size(); j++){
                if(j == triangle[i].size() - 1)
                    dp[j] += triangle[i][j];
                else
                    dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
            }
        }
        // 取得最小值
        int res = INT_MAX;
        for(auto num: dp)
            if(num < res)
                res = num;
        return res;
    }
};