leetcode-120-线性DP-三角形最小路径和

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 动态规划 空间复杂度O(n^2)
// 自顶向下求解
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();

        if(triangle.empty()) return 0;
        if(n == 1) return triangle[0][0];

        // dp[i][i] = x 表示走到第i行第j列时的最小路径和
        vector<vector<int>> dp(n, vector<int>(n, -1));
        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] = dp[i-1][j] + triangle[i][j];
                else if(j == i) dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                else dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }

        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }
};


// 动态规划 空间复杂度O(n^2)
// 自底向上求解
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();

        if(triangle.empty()) return 0;
        if(n == 1) return triangle[0][0];
        
        // 自底向上，先初试化最后一行
        // dp[i][i] = x 表示走到第i行第j列时的最小路径和
        vector<vector<int>> dp(n, vector<int>(n, -1));
        dp[n-1] = triangle[n-1];

        for(int i = n-2; i >= 0; --i){
            for(int j = 0; j <= i; ++j){
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
            }
        }

        return dp[0][0];
    }
};

// 动态规划 空间复杂度O(n)
// 自底向上求解
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();

        if(triangle.empty()) return 0;
        if(n == 1) return triangle[0][0];

        // 自底向上求解，dp保存最后一行数值，然后逐次向上求解
        vector<int> dp(triangle.back());

        for(int i = n-2; i >= 0; --i){
            for(int j = 0; j <= i; ++j){
                dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
            }
        }

        return dp[0];
    }
};