[关闭]
@liweiwei1419 2019-01-18T06:05:55.000000Z 字数 2485 阅读 833

“动态规划”第 2 节:第 1 个动态规划问题的 3 种实现

动态规划


例题

例1:LeetCode 第 70 题:Climbing Stairs

题目要求:有一个楼梯,总共有 阶台阶。每一次,可以上一个台阶,也可以上两个台阶。问,爬上这样的一个楼梯,一共有多少不同的方法?

思路分析:我们可以画出这个问题的递归结构图。

image-20190118134508625

我们可以发现:1、该图是一个树形结构图;2、有重叠子问题。

image-20190118134524465

递归实现

Java 代码:

  1. public class Solution {
  2. public int climbingStairs(int n) {
  3. if (n <= 0) {
  4. return 1;
  5. }
  6. int res = climbinng(n);
  7. return res;
  8. }
  9. private int climbinng(int n) {
  10. if (n == 1) {
  11. return 1;
  12. }
  13. if (n == 2) { // 方法1:一个台阶,一个台阶;方法2:一次上两个台阶
  14. return 2;
  15. }
  16. // 接下来就是看图说话了(乘法计数原理)
  17. return climbinng(n - 1) * 1 + climbinng(n - 2) * 1;
  18. }
  19. }

说明:从第 1 节我们可以知道,这一版代码有大量的“重叠子问题”,我们应该加上缓存。

使用记忆化搜索

  1. public class Solution {
  2. private int[] memory;
  3. public int climbingStairs(int n) {
  4. if (n <= 0) {
  5. return 1;
  6. }
  7. memory = new int[n + 1];
  8. for (int i = 0; i < n + 1; i++) {
  9. memory[i] = -1;
  10. }
  11. int res = climbinng(n);
  12. return res;
  13. }
  14. private int climbinng(int n) {
  15. if (n == 1) {
  16. return 1;
  17. }
  18. if (n == 2) { // 方法1:一个台阶,一个台阶;方法2:一次上两个台阶
  19. return 2;
  20. }
  21. // 接下来就是看图说话了(乘法计数原理)
  22. if (memory[n] == -1) {
  23. memory[n] = climbinng(n - 1) * 1 + climbinng(n - 2) * 1;
  24. }
  25. return memory[n];
  26. }
  27. }

说明:递归的代码写起来比较繁琐,我们可以用于思考。另一种写法就是“自底向上”,即“动态规划”。“动态规划”的代码是比较简洁的。

使用动态规划

Java 代码:

  1. public class Solution2 {
  2. public int climbingStairs(int n) {
  3. if (n <= 0) {
  4. return 1;
  5. }
  6. if (n == 1) {
  7. return 2;
  8. }
  9. int[] memory = new int[n + 1];
  10. for (int i = 0; i < n + 1; i++) {
  11. memory[i] = -1;
  12. }
  13. for (int i = 2; i < n + 1; i++) {
  14. memory[i] = memory[i - 1] + memory[i - 2];
  15. }
  16. return memory[n + 1];
  17. }
  18. }

练习

练习1:LeetCode 第 120 题: 三角形最小路径和

要求:给定一个三角形的数字阵列,选择一条自顶向下的路径,使得沿途的所有数字之和最小。(每一步只能移动到相邻的格子中。)
image-20190118140008499

分析:关键的地方在于“从上到下”和“从下到上”思考的路径不同,导致解答的复杂程度不同。

“从上到下”:最边上的点只能从最边上的点走过来。

“从下到上”:每一点都有两个孩子:左孩子和右孩子,可以少掉很多讨论。

Python 实现:

  1. class Solution:
  2. def minimumTotal(self, triangle):
  3. """
  4. :type triangle: List[List[int]]
  5. :rtype: int
  6. """
  7. if len(triangle) == 0:
  8. return 0
  9. # 这里要多留一个位置,防止数组越界
  10. dp = [0] * (len(triangle) + 1)
  11. for i in range(len(triangle) - 1, -1, -1):
  12. for j in range(i + 1):
  13. # 【关键】自底向上,每个元素都有左右孩子,就相当于在最后一行加上一行 0
  14. dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
  15. print(dp)
  16. return dp[0]
  17. if __name__ == '__main__':
  18. triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
  19. # triangle = [[-10]]
  20. s = Solution()
  21. res = s.minimumTotal(triangle)
  22. print(res)

二刷的时候,写的代码:

  1. class Solution:
  2. def minimumTotal(self, triangle):
  3. """
  4. :type triangle: List[List[int]]
  5. :rtype: int
  6. """
  7. l = len(triangle)
  8. if l == 0:
  9. return 0
  10. dp = triangle[-1]
  11. for i in range(l - 2, -1, -1):
  12. for j in range(len(triangle[i])):
  13. dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
  14. return dp[0]

练习2:LeetCode 第 64 题:最小路径和

要求:给出一个 m * n 的矩阵,其中每一个格子包含一个非负整数。寻找一条从左上角到右下角的路径,使得沿路的数字和最小。

参考解答:

  1. class Solution(object):
  2. def minPathSum(self, grid):
  3. """
  4. :type grid: List[List[int]]
  5. :rtype: int
  6. """
  7. m = len(grid)
  8. if m == 0:
  9. return 0
  10. n = len(grid[0])
  11. for col in range(1, n):
  12. # 第 0 行特殊处理
  13. grid[0][col] += grid[0][col - 1]
  14. for row in range(1, m):
  15. grid[row][0] += grid[row - 1][0]
  16. for col in range(1, n):
  17. grid[row][col] += min(grid[row - 1][col], grid[row][col - 1])
  18. return grid[-1][-1]

(完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注