【数据结构和算法】三、动态规划原理讲解与实战演练

目录

1、什么是动态规划？

2、动态规划实战演练

2.1 力扣题之爬楼梯问题

（1）解题思路1:

（2）解题思路2:

（3）动态规划（DP）：解题思路

（4）动态规划理论

2.2 力扣题之海盗船长

（1）解题思路1:

（2）解题思路2:

（3）动态规划：解题思路3:

---

1、什么是动态规划？

        动态规划（Dynamic Programming，DP）是把复杂问题分解为简单的子问题的求解方法。

        动态规划的基本思想虽然简单，但分解的子问题很多都不一样。所以需要多做一些练习，接触并了解各种子问题及分解的思路，结合着不同数据结构，才能逐渐掌握DP的技巧。

        所以，DP归纳起来就是多做练习，多思考，逐渐摸索题目的思考逻辑和优化思路。才能掌握使用DP解题的技巧。

---

   从实际问题出发，分几步走，不断练习、迭代熟练：

1. 暴力求解（枚举）
2. 拆分子问题（DP）解法
3. DP原理与题型相结合的分析

2、动态规划实战演练

2.1 力扣题之爬楼梯问题

以力扣著名的题“爬楼梯”为例子：

• 爬楼梯问题： . - 力扣（LeetCode）

  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

  每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  示例 1：

  输入：n = 2
  输出：2
  解释：有两种方法可以爬到楼顶。
  1. 1 阶 + 1 阶
  2. 2 阶
  

  示例 2：

  输入：n = 3
  输出：3
  解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶
  

  提示：

  • 1 <= n <= 45

  （1）解题思路1:

  暴力求解，排列所有1，2的组合。

  寻找总和为n的，不同数字长度的组合。

  from itertools import productdef climbStairs(n):pms = []for rep in range(1,n+1):permutations = list(product([1,2],repeat=rep))for pm in permutations:if sum(pm) == n:pms.append(pm)return len(pms)
  

  ※ itertools是python为高效循环而创建迭代器的函数库 。product就是一个笛卡尔积（嵌套for循环）功能实现的函数。

  • 时间复杂度O(n^3)
  • 空间复杂度O(n)

  （2）解题思路2:

  问题寻找的是爬楼梯的方法数量，而不是具体统计每次走几阶。

  所以问题关注的是每次爬1阶、爬2阶两种走法的组合上。

  假设n=3，可以直接排列一下相应的组合

  3 = 1 + 1 + 1
  3 = 2 + 1
  3 = 1 + 2
  

  简单直观，但我们要寻找的爬楼梯的规律。似乎还没有发现，继续增加n的数量~

  当n=4：

  4 = 1 + 1 + 1 + 1
  4 = 2 + 1 + 1
  4 = 1 + 2 + 14 = 1 + 1 + 2
  4 = 2 + 2
  

  当n=5时：

  5 = 1 + 1 + 1 + 1 + 1
  5 = 2 + 1 + 1 + 1
  5 = 1 + 2 + 1 + 15 = 1 + 1 + 2 + 1
  5 = 2 + 2 + 15 = 1 + 1 + 1 + 2
  5 = 2 + 1 + 2
  5 = 1 + 2 + 2
  

          排列组合的方式，让我们似乎观察到了数值的规律。那就是n阶的走法，包含了n-1阶和n-2阶的走法。且 n阶的走法 = (n-1)阶走法 + (n-2)阶走法

  简单的循环遍历就可以完成走法的累加：

  n = 5
  n1,n2 = 1,2  # n=1和n=2情况下的走法
  res = 0
  for i in range(3, n+1):  # 从n=3时开始，直到nres = n1 + n2n1 = n2n2 = res
  print(res)
  

  测试下n=6，结果(n-1) + (n-2) = 8 + 5 = 13

  还可以转换为递归写法

  def climbStairs(n):if n <= 1:return 1return climbStairs(n-1) + climbStairs(n-2) 
  

  至此，就是暴力算法的解题思路，所有可能的组合都做一遍。

  （3）动态规划（DP）：解题思路

  依据上面算法特征分析的基础上，使用一个数组动态存储n的计算结果。

  初始化数组，预先存入n-1和n-2的结果

  def climbStairs(n):if n <= 1:return ndp = [i for i in range(n+1)]for i in range(3,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[-1]
  

  上面代码中的dp就是我们提到的数组，其中dp[i] = dp[i-1] + dp[i-2]。

  循环执行完成后，数组中最后一次计算的结果就是爬n阶楼梯的方法数。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

  对于空间复杂度，还可以进一步优化。由于我们只考虑n以及n-1、n-2的值。所以，中间的过程值可以丢弃。定义一个固定长度的数组，每次计算结果动态覆盖，如下：

  def climbStairs(n):if n <= 1:return ndp = [0,1,2]for i in range(3,n+1):sum = dp[1] + dp[2]dp[1] = dp[2]dp[2] = sumreturn dp[2]
  

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

  （4）动态规划理论

          学习动态规划算法，是从多种题解的思路中学习和发现。众多技术高手都给出了思路和技巧，但从实际出发，建议还是先埋头做题，积累了练习和分析思考后，再进行看高手的总结和归纳才会有“英雄所见略同”的共识。

  在这之前，针对每道题目的分析，希望能思考如下的几个问题：

  • 题目计算的目标是什么

    走台阶问题的目标是求走法组合总数。

  • 计算分解的子问题是什么

    (n-1)阶走法 、(n-2)阶走法就是n阶走法的子问题 ****

  • 转移方程是否是子问题的组合

    转移方程上面已经写出来了 f(n) = f(n-1)+f(n-2) 。

  • 能否优化

    使用动态数组或字典来存储中间结果，可以有效的减少重复计算的复杂度。

    当然，涉及到使用数组等容器来实现计算和优化时，还会接触到背包问题。

2.2 力扣题之海盗船长

问题：海盗船长：. - 力扣（LeetCode）

海盗船长：船长从坐标为(0,0)的位置出发，每次只能向x轴,y轴正方向走一步，求走到x,y点有几种走法?

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：n = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 10^9

（1）解题思路1:

从[0,0]到[x,y]，是一个从矩阵左上角向右、向下探索的过程。

想要到达[x,y]位置，必然经过[x-1,y]或者[x,y-1]

所以，路径问题的分解就是求[x , y] = [x-1,y] + [x,y-1]

设 m,n = 3,7 暴力解法

results = {}def path_count(x, y):# results = {}if x == 1 or y == 1:results[(x,y)] = 1return 1results[(x,y)] = path_count(x-1,y) + path_count(x,y-1)return results[(x,y)]print(path_count(3,7))

时间复杂度：O(mn)

空间复杂度：O(n)

（2）解题思路2:

观察上面的方案，可以发现分解的路径实际上存在着大量重复的计算

print(results)

我们可以思考：走到results中(m,n)位置的上一步，一定是(m-1,n),(m,n-1),(m-1,n-1)的位置。

这其中(m-1,n-1)走过的路径中，就包含了(m-1,n)和(m,n-1)走过的路径。

以此类推，所有(m-2,n-2)的路径中，也就包含了(m-1,n-1), (m-1,n), (m,n-1) …… 如此嵌套。我们把计算结果存储在results里面，再次遇到相同的计算时，就直接把结果提取出来。

def path_count(x, y):if x == 1 or y == 1:results[(x,y)] = 1return 1# 查找重复节点，直接返回计算后结果if (x,y) in results:return results[(x,y)]results[(x,y)] = path_count(x-1,y) + path_count(x,y-1)return results[(x,y)]

（3）动态规划：解题思路3:

动态规划方式实现：

转移方程：f(x,y) = f(x-1,y) + f(x, y-1)

分两步实现：

1. 计算“到达”每个位置所需要的步数(初始为1)

   m,n = 3,7
   path_counts = [[1] * n for j in range(m)]
   for i in range(m):for j in range(n):print(path_counts[i][j], end=' ')print()
   

2. 计算从起始位置，到达当前位置，步数的累加和

   for x in range(1,m):for y in range(1,n):path_counts[x][y] = path_counts[x-1][y] + path_counts[x][y-1]print(path_counts[m-1][n-1])
   

完整代码：

def path_count(x, y):path_counts = [[1] * y for j in range(x)]for i in range(1,x):for j in range(1,y):path_counts[i][j] = path_counts[i-1][j] + path_counts[i][j-1]return path_counts[x-1][y-1]