120. Triangle

Leetcode link

解题思路

本题要求我们求出一条从三角形顶部走到底部的最小路径和，且每一步只能移动到下一行的相邻节点上

很明显是一个动态规划的题目，我们需要一个二维数组 dp[i][j] 来记录走到 (i, j) 的最小路径和

我们首先得找到它的状态转移方程，总共有三种情况：

• j = 0：也就是在第 i 行的最左侧，这个时候只有 (i - 1, 0) 能走到，所以 dp[i][j] = dp[i-1][0] + Triangle[i][0]
• j = i：也就是在第 i 行的最右侧，这个时候只有 (i - 1, i - 1) 能走到，所以 dp[i][j] = dp[i-1][i-1] + Triangle[i][i]
• j < i & j > 0：也就是在中间部分，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + Triangle[i][j]

最后当我们遍历完了 Triangle 之后，只要求 dp[i] 数组的最小元素就好

C++

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];
        }
        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }
};

Javascript

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let len = triangle.length;
    let dp = new Array(len).fill(0).map(_=>_ = new Array(len).fill(0));
    dp[0][0] = triangle[0][0];
    for(let i = 1;i < len;i++) {
        dp[i][0] = dp[i - 1][0] + triangle[i][0];
        for(let j = 1;j < i;j++) {
            dp[i][j] = Math.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 Math.min(...dp[len - 1]);
};