Leetcode_14 天算法入门_day12

Posted on | Edited on | In ,
| 4.5k | 37 mins.

今天的主题是动态规划（dp），之前就想琢磨一下这类问题了。

不过，今天应该都是比较简单的 dp 问题。

70. Climbing Stairs

Analysis

这是个很经典的 dp 入门问题，每次跳台阶可以选择跳 1 阶或 2 阶，当前的选择会影响到下一跳的选择。显然，如果只用跳 1 阶，那么只有 1 种跳法；如果跳 2 阶，就有 2 种跳法，由此可得：$dp[1] = 1, dp[2] = 2$。此时，手动算一下跳 3 阶的情况，也即：1 1 1、1 2和2 1这 3 种情况，则$dp[3] = 3$，同理，$dp[4] = 5$。这样就可以得到递归公式（也叫状态转移方程）：$dp[i] = dp[i - 1] + dp[i - 2]$。想到这里会发现，这是个 fibonacci 数列问题。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int climbStairs(int n) {
        int dp[50];
        dp[1] = 1, dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

198. House Robber

Analysis

这个题算是上面那个题的变式，从后往前算可能会稍微好理解一点？
假设总共有 n 个数字，对于最后一个数字，$dp[n - 1] = nums[n - 1]$，$dp[n - 2] = nums[n - 2]$，倒数第 3 个数就是$dp[n - 3] = nums[n - 3] + dp[n - 3 + 2]$，但是倒数第四个数就不一样了。题目只是要求不能选择相邻的，没说不能隔 2 个选，所以$dp[n - 4] = nums[n - 4] + max(dp[n - 4 + 2], dp[n - 4 + 3])$，从而可以得到状态转移方程：$dp[i] = nums[i] + max(dp[i + 2], dp[i + 3])$。

Code

one dimension

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[105], size = nums.size();
        if(size == 1) return nums[0];
        dp[size - 1] = nums[size - 1], dp[size - 2] = nums[size - 2];
        int Max = dp[size - 1] > dp[size - 2] ? dp[size - 1] : dp[size - 2];
        if(size == 2) return Max;
        dp[size - 3] = nums[size - 3] + dp[size - 1];
        Max = Max > dp[size - 3] ? Max : dp[size - 3];
        for(int i = size - 4; i >= 0; i--) {
            dp[i] = nums[i] + max(dp[i + 2], dp[i + 3]);
            if(dp[i] > Max) Max = dp[i];
        }
        return Max;
    }
};

当然，也可以从前往后算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0;
        if(size == 1) return nums[0];
        int dp[105];
        dp[0] = nums[0], dp[1] = max(dp[0], nums[1]);
        for(int i = 2; i < size; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[size - 1];
    }
};

two dimension

这个题其实也可以从 2 维 dp 的角度来考虑。dp[i][0]表示第 i 家偷，dp[i][1]表示第 i 家不偷，每一次偷得到的值是相邻一家未偷与当前这一家的数字之和，这是题目要求的相邻。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[105][2], size = nums.size();
        dp[0][0] = nums[0], dp[0][1] = 0;
        for(int i = 1; i < size; i++) {
            dp[i][0] = dp[i - 1][1] + nums[i];
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);
        }
        return max(dp[size - 1][0], dp[size - 1][1]);
    }
};

感觉二维 dp 好像还难理解一点？

120. Triangle

Analysis

这个题也是经典的 dp 求解数塔问题。
采用自底向上的思路来进行 dp，设这个数塔有 n 层，那么$dp[n][j] = triangle[n][j]$，此时，$dp[n][j]$就是这个问题的边界，也就是最底层的那一排数。继续向上一层，$dp[n - 1][j]$就是$min(dp[n][j], dp[n][j + 1]) + triangle[n - 1][j]$，那么状态转移方程就是$dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1])$。

Code

bottom-up

按照上面的思路，可以得到下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* bottom-up */
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>> dp = triangle;
        int size = triangle.size();
        for(int i = size - 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];
    }
};

top-down

在按照自顶向下的思路做一下：
显然自顶向下时，$dp[0][0] = triangle[0][0]$就是边界
第二行的第一个数只能从其右上的数往下，所以 $dp[i][0] = dp[i - 1][0] + triangle[i][0]$；同理，第二行的最后一个数就是 $dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]$。
那么中间的数，就是：$dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]$，这就是这个题的状态转移方程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* top-down */
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>> dp = triangle;
        int size = triangle.size();
        for(int i = 1; i < size; 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[size - 1].begin(), dp[size - 1].end());
    }
};

Summary

今天的三道 dp 题，感觉都不是难题，应该都是十分经典的入门题，做的挺有意思，特别是推导状态转移方程这里。稍微细想一下，这种题好像理解了题目意思，就知道应该是 dp 题了？另外，从这 3 个题来讲，dp 题的做法应该很多，不过都大同小异，首先要找到边界，明确 dp 数组下标的含义，然后想办法推导出状态转移方程就差不多了。多说无益，需要再来点题目练练手。

Buy me a coffee ? :)
0%