【leetcode】120. 三角形最小路径和（triangle）（DP）[中等]

链接

https://leetcode-cn.com/problems/triangle/

耗时

解题：20 min
题解：13 min

题意

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

思路

很奇怪的思路，不常规，写出这个思路代码是因为我之前是用 DFS 做的（T 了），然后直接改的 DP，就变成这样了。

当前状态 dp[i][j] 可以转移到的状态有两个 dp[i+1][j] 和 dp[i+1][j+1]，分别由当前状态 最小路径和 加上 下一状态对应的节点值 转移到。因为有些状态会两次转移到，所以取最小值。

状态转移方程：

d p [ i + 1 ] [ j ] = m i n ( d p [ i + 1 ] [ j ] , d p [ i ] [ j ] + t r i a n g l e [ i + 1 ] [ j ] ) ; d p [ i + 1 ] [ j + 1 ] = m i n ( d p [ i + 1 ] [ j + 1 ] , d p [ i ] [ j ] + t r i a n g l e [ i + 1 ] [ j + 1 ] ) ; dp[i+1][j] = min(dp[i+1][j], dp[i][j]+triangle[i+1][j]); \\ dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1]); dp[i+1][j]=min(dp[i+1][j],dp[i][j]+triangle[i+1][j]);dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+triangle[i+1][j+1]);

最后答案即为最后一行的最小路径和 dp[n-1][i] 的最小值。

时间复杂度： O ( n 2 ) O(n^2) O(n2)

AC代码

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