Code & Func

第5天，早起刷题的一天。

一道典型的动态规划题，动态规划的题目一般都可以分为多步走，一旦执行完一步，走下一步时可以利用之前几步的结果来快速的选择下一步要怎么走。

关键就是要找出怎么利用之前几步的结果。

如这里的，我们要知道走到最后一行的最短路径，那么如果我们已经知道了走到倒数第二行（即上一行）的最短路径，我们就可以很快的算出走到最后一行的最短路径，即：

dp[i][j] = min(dp[i-1][j-1], dp[i][j], dp[i][j+1]) + A[i][j]

然后很顺手的我们可以用两个数组来优化代码的空间复杂度，即把二维数组转成两个一维数组。

因此代码如下:

1
class Solution {
2
public:
3
    int minFallingPathSum(vector<vector<int>>& A) {
4
        int h = A.size(), w;
5
        if (h == 0) return 0;
6
        w = A[0].size();
7

8
        vector<int> dp0 = A[0];
9
        vector<int> dp1(w, INT_MAX);
10

11
        for(int i = 1; i < h; i++) {
12
            for(int j = 0;j < w; j++) {
13
                dp1[j] = INT_MAX;
14
                if (j > 0) dp1[j] = min(dp0[j-1], dp1[j]);
15
                dp1[j] = min(dp0[j], dp1[j]);
12 collapsed lines
16
                if (j + 1 < w) dp1[j] = min(dp0[j+1], dp1[j]);
17
                dp1[j] += A[i][j];
18

19
            }
20
            swap(dp1, dp0);
21
        }
22

23
        int res = INT_MAX;
24
        for(auto &i: dp0) res = min(res, i);
25
        return res;
26
    }
27
};