动态规划

Posted on Edited on

动态规划（dynamic planning）问题的一般形式就是求最值。比如说让你求最⻓递增子序列、最小编辑距离等等。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。但是动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。因为存在「重叠子问题」，所以一定会具备「最优子结构」，只有列出正确的「状态转移方程」才能正确地穷举。

三大步骤

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。

  1. 定义 dp 数组

首先判断是一维数组还是二维数组，再判断 dp[i] 或者 dp[i][j] 中 i 和 j 的含义。

  1. 找出数组元素之间的关系式（状态转移方程）

这一步是最困难的，如果是一维数组，我们一般寻找 dp[n] 、 dp[n-1] 、 dp[n-2] 之间的关系，如果是二维数组，一般寻找 dp[i][j] 、 dp[i-1][j] 、 dp[i][j-1] 、 dp[i-1][j-1] 之间的关系。

  1. 找出初始值。

基于状态转移方程，写出它的边界值，例如 dp[1] 、 dp[1][1] 等初始可得的值。

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？LeetCode地址

  1. 显然 dp 数组为dp[n]， n 为楼梯阶数

  2. 思考 dp[n] 应该等于什么，也就是思考他的子问题（子问题可以是一组）是什么。分析题意子问题应该是 dp[n - 1] 和 dp[n - 2]，他们和 dp[n] 的关系是：dp[n] = dp[n - 1] + dp[n - 2]。

  3. 写出初始值，即dp[1] = 1和dp[2] = 2

  4. 写遍历方法的时候需要注意，从小到大的填写dp数组，因为求dp[n]的值，必须先求其子问题的值

1
2
3
4
5
6
7
8
9
10
11
12
13
def climbStairs(n):
  # 最小实现
  if n <= 2: return n

  # 创建 dp 数组
  dp = [0] * (n + 1)
  dp[1] = 1
  dp[2] = 2

  for i in range(3, n + 1):
    # 循环中使用状态转移方程
    dp[i] = dp[i - 1] + dp[i - 2]
  return dp[n]

三角形最小路径和

LeetCode地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def minimumTotal(triangle):
  n = len(triangle)
  f = [[0] * n for _ in range(n)]
  f[0][0] = triangle[0][0]

  for i in range(1, n):
      # 最左边的值来自最左侧的数据 triangle[i][0]
      f[i][0] = f[i - 1][0] + triangle[i][0]
      # 中间的值来自左侧或者右侧的最小值
      for j in range(1, i):
          f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
      # 最右边的值来自最右侧的数据 triangle[i][i]
      f[i][i] = f[i - 1][i - 1] + triangle[i][i]
  
  return min(f[n - 1])

滚动数组

当状态转移方程为 dp[i][j] = dp[i][j - 1] + dp[i -1][j] 时，可以使用滚动数组进行优化，降低空间复杂度，优化之后为 dp[j] += dp[j-1] 。