Leetcode 120.Triangle

原题地址

https://leetcode.com/problems/triangle/description/

题意

想象一个杨辉三角那样的三角形（是指形状，数字可以自己输入），从三角形的顶点开始每次往左下方或右下方移动，一直到最底层，把经过的元素相加，求这个过程的和的最小值。

思路

动态规划，建表，dp[i][j]表示到triangle[i][j]这个元素时的最小和。

代码

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