leetcode题解-931-下降路径最小和

发表于 | 更新于 | 分类于

题目

My way

1.二维DP

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
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int m = A.size();
        int n = A[0].size();
        vector<vector<int>> dp(A);

        // base case
        for (int j = 0; j < n; ++j)
        {
            dp[0][j] = A[0][j];
        }

        // 
        for (int i = 1; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (j - 1 == -1)
                {
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + A[i][j];
                }
                else if (j + 1 == n)
                {
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + A[i][j];
                }
                else
                {
                    dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]) + A[i][j];
                }
            }
        }

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

2.一维DP

可以将二维DP压缩至一维DP处理。