Python 算法之 动态规划详解
Python 算法之 不同子序列文章目录Python 算法之 不同子序列动态规划动态规划经典问题背包问题给出题目参考资料相关博客动态规划动态规划，英文名 Dynamic Programming，简写为 DP，是寻找多分支下最优解的过程动态规划工作原理：先解决相对简单的子问题，再逐步解决大问题动态规划是一个难以理解的概念，真的动态规划经典问题背包问题假设张三要去野营，他准备了以下物品：每样东西都有相
Python 算法之 动态规划
文章目录
动态规划是个啥🤔
动态规划（Dynamic Programming），简写为 DP，是寻找多分支下最优解的过程
动态规划工作原理：
先解决相对简单的子问题，再逐步解决大问题
根据下面这些问题，来了解一下什么是动态规划🙄
动态规划经典问题🤓
背包问题
背包问题1 是动态规划中中一个很经典的问题，这个问题生动有趣，所以我放在第一个来讲
假设张三要去野营，他准备了以下物品：
| 物品 | 重量 | 价值 |
|---|---|---|
| 水 | 3斤 | 10 |
| 书 | 1斤 | 3 |
| 食物 | 2斤 | 9 |
| 小刀 | 3斤 | 4 |
| 衣物 | 2斤 | 5 |
| 手机 | 1斤 | 10 |
每样东西都有相应的价值，可呆呆的他在收拾背包时发现，他的背包 最大容量只有6斤，装不下所有的东西，只能从这堆东西中挑选 组合价值 最高的物品
关键点
- 约束条件： 将背包的容量大小(承重)划分成不同容量大小的子背包，计算每个子背包的最大价值
- 物品重量不能超过当前背包容量，不可能将重量为5斤的物品放进容量为2斤的背包里，机器可不能像人一样会自己识别大小，这看起来可笑的问题确实会发生，得加上判断语句
只能拿一次物品的情况下
每个子问题取得一次物品，就不能再取相同的物品，要么这个要么这个，拿了就没
比如此时 背包容量为6斤，拿了一瓶水后 占用了背包容量3斤，剩余容量为3斤 我要么再拿一本书和一件衣服(1+2)，要么再拿食物和一部手机(2+1)等，不可能再去拿一瓶水
def dynamic_p() -> list:
items = [ # 物品项
{"name": "水", "weight": 3, "value": 10},
{"name": "书", "weight": 1, "value": 3},
{"name": "食物", "weight": 2, "value": 9},
{"name": "小刀", "weight": 3, "value": 4},
{"name": "衣物", "weight": 2, "value": 5},
{"name": "手机", "weight": 1, "value": 10}
]
max_capacity = 6 # 约束条件为 背包最大承重为6
dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]
for row in range(1, len(items) + 1): # row 代表行
for col in range(1, max_capacity + 1): # col 代表列
weight = items[row - 1]["weight"] # 获取当前物品重量
value = items[row - 1]["value"] # 获取当前物品价值
if weight > col: # 判断物品重量是否大于当前背包容量
dp[row][col] = dp[row - 1][col] # 大于直接取上一次最优结果 此时row-1代表上一行
else:
# 使用内置函数max()，将上一次最优结果 与 当前物品价值+剩余空间可利用价值 做对比取最大值
dp[row][col] = max(value + dp[row - 1][col - weight], dp[row - 1][col])
return dp
dp = dynamic_p()
for i in dp: # 打印数组
print(i)
print(dp[-1][-1]) # 打印最优解的价值和
可重复拿取物品的情况下
先思考一个问题，为什么上面的代码可以不重复拿去？
那是因为，我们是根据 当前物品的价值+剩余空间的价值 来更新最优解，可这个剩余空间价值是通过上一行来获取的，并未加上当前的商品价值，因此只需要加上当前的商品价格作为参考，即在当行获取最优解
def dynamic_p() -> list:
items = [ # 物品项
{"name": "水", "weight": 3, "value": 10},
{"name": "书", "weight": 1, "value": 3},
{"name": "食物", "weight": 2, "value": 9},
{"name": "小刀", "weight": 3, "value": 4},
{"name": "衣物", "weight": 2, "value": 5},
{"name": "手机", "weight": 1, "value": 10}
]
max_capacity = 6 # 约束条件为 背包最大承重为6
dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]
for row in range(1, len(items) + 1): # row 代表行
for col in range(1, max_capacity + 1): # col 代表列
weight = items[row - 1]["weight"] # 获取当前物品重量
value = items[row - 1]["value"] # 获取当前物品价值
if weight > col: # 判断物品重量是否大于当前背包容量
dp[row][col] = dp[row - 1][col] # 大于直接取上一次最优结果 此时row-1代表上一行
else:
# row-1 为上一行，row为本行，若要重复拿取，只需要在目前物品所在的那一行寻找最优解即可
dp[row][col] = max(value + dp[row][col - weight], dp[row - 1][col])
return dp
dp = dynamic_p()
for i in dp: # 打印数组
print(i)
print(dp[-1][-1]) # 打印最优解的价值和
可以看到，创建二维数组的时候，行列数都加了一🙄
- 每个单元格的取值，要么是来自 上一 CELL(单元格) 的值，要么来自 当前物品的价值+剩余容量价值，这些取值都离不开上一行的最优解值，可二维数组中第一行的每一个单元格(即子问题) ，都没有上一个 CELL 的值，那就需要在第一行前再插入每个 CELL 都为0的一行
- 数组的索引从0开始，1的索引在数组第二个位置，为方便编写和理解，多增一行一列，索引为0的行列不做变动
根据背包问题可以得到以下启示😮
-
二维数组(网格、DP Table)： 每个 CELL 都是一个子问题，要考虑如何将问题分解成一个个子问题，每个子问题的最优解存储在 CELL 里
-
动态规划没办法处理只拿物品的一部分，要么全部拿走，要么不拿
-
行的排列顺序对结果的影响无关紧要
如图所示最后的最优解都是 29 -
问题的最优解不一定要把背包装满
如果遇到一个物品的价值比其他物品都要高时，那肯定会装下此物品，可在装下此物品后剩余空间不足于再装下其他物品，就会出现背包没装满的情况
如现有背包容量的最大容量还是为 6斤，有个 5.5斤 重，价值为100的物品，这个物品比其他所有物品价值都要高，装上背包后，剩余 0.5斤 容量别的什么都装不下
子串、子序列又是啥🤔
最长递增子序列
最长递增子序列 ( longest increasing subsequence )4，简写为 LIS
指的是在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，且这个子序列长度是最长的
给定一个数组，nums = [6, 10, 9, 2, 3, 6, 10, 661, 66]，这个数组的最长递增子序列是 [2, 3, 6, 10, 66]，算法中的输出结果应为 5
关键点：
-
最简单的情况下（base case），最短的子序列应该为自己，即为 1
-
如何根据dp[ i ] 前面的结果来推出 dp[[ i ] 呢？
加一个循环，遍历nums[ i ]前面的值，如果存在比nums[ i ]小的值，则继承dp[ i ]上的结果并 加一
需要注意的是：比 nums[i] 小的子序列可能不只一个，需要继承的是最大值for k in range(i): if nums[i] > nums[k]: dp[i] = max(dp[i], dp[k]+1)
结合上述内容，完整代码为👇🏻
def length_lis(nums: list) -> int:
length = len(nums) # 获取nums数组长度
dp = [1] * length # 定义 dp table
for i in range(len(nums)):
for k in range(i):
if nums[i] > nums[k]: # 寻找前面那些比当前数值小的子序列
dp[i] = max(dp[i], dp[k]+1) # 比当前数值小的数可能不只一个，取最大值
return max(dp) # 最大的值就是最长的子串
nums = [6, 10, 9, 2, 3, 6, 10, 661, 66]
print(length_lis(nums))
DP Table 的维度
可以看到，这里关于递增的问题使用到的都是一维数组，而最开始讲到的背包问题却使用了二维数组
数组维度并非是固定的，要根据问题提供数据的复杂度来选择 DP Table 的数组维度
最长公共子串、子序列
最长公共子串5
最长公共子串（Longest common substring）
是寻找两个或多个已知字符串最长的子串
此问题与最长公共子序列问题的区别在于 子序列不必是连续的，而子串却必须是
这里有两个字符串，分别是 bear 和 beear，他们两的最长公共子串值是多少呢？🙄
def dynamic_p(s1, s2) -> list:
r, c = len(s1), len(s2)
dp = [[0] * (c+1) for _ in range(r+1)]
for row in range(r):
for col in range(c):
if s1[row] == s2[col]:
dp[row+1][col+1] = dp[row][col] + 1 # 对左上角CELL值+1
else:
# 匹配不成功清0，这里可以不用到else，因为默认值就为0
dp[row+1][col+1] = 0
return dp
arr = []
dp = dynamic_p("bear", "beear")
for i in dp:
arr.extend(i)
print(i) # 打印数组
print(f"最长公共子串为:{max(arr)}")
- 当匹配成功时，此时单元格的值应为左上角CELL的值加一
- 匹配不成功时，应当为零
如何理解 DP[i-1][j-1] + 1
如 beear 和 bear，此时 b 为 e 的上一个字符，若e匹配成功了，那就检查它的上一个字符 b 有没有匹配成功，上一个字符 b 在左上角单元格的位置，若 b 也匹配成功了，那在此基础上加一，保存连续的记录状态
最长长公共子序列6
最长公共子序列（Longest Common Subsequence），简写为 LCS
是在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题，
这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。
说人话就是
- 计算两个字符串中 能连在一块字符的最长长度
比如输入
str1="abcdefg"，str2="edge"，其中最长的公共子序列为[e, g]，算法应输出 2
比起获取最长公共子串，获取最长公共子序列，容易想到是暴力方法
def dynamic_p(s1, s2) -> int:
res = set() # 利用集合进行去重
for i in s1:
for k in s2:
if i == k:
res.add(k)
return len(res)
print(dynamic_p("beear", "bear"))
如何使用动态规划
要记住动态规划原理是：先解决相对简单的子问题，再逐步解决大问题
那如何将问题划分成子问题呢？约束条件又是什么？
将字符串 s1 和字符串 s2 拆开，如 “b” 与 “be”、“b” 与 “bea”、“b” 与 “bear” 的最长公共子序列，这就是一个个子问题，将其表现为二维数组(网格)，为下图所示👇
关键点：
DP[1][2] = 1代表 “be” 与 “b” 的最长公共子序列为 1，DP[3][2] = 2代表 “be” 与 “bea” 的最长公共子序列为 2，DP[3][2] = 2代表 “bee” 与 “bea” 的最长公共子序列为 2- 最简单的情况(base case) 是没有公共子序列，即为 0
def dynamic_p(s1, s2) -> list:
r, c = len(s1), len(s2)
dp = [[0] * (c+1) for _ in range(r+1)]
for row in range(r):
for col in range(c):
if s1[row] == s2[col]:
dp[row+1][col+1] = dp[row][col] + 1 # 上一个字符串最长公共子序列再加一
else:
# 在左方CELL和上方CELL中选择 子问题中最长公共子序列 较长的那个
dp[row+1][col+1] = max(dp[row+1][col], dp[row][col+1])
return dp
dp = dynamic_p("bear", "beear") # 打印数组
for i in dp:
print(i)
print(f"最长公共子序列为:{dp[-1][-1]}")
给出题目
由于篇章实在过长，这里将每个问题分为单独的一篇博客🙄
最大子数值问题
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组，求所有子数组的和的最大值
比如输入
nums = [-2,1,-3,4,-1,2,1,-5,4]，其中的最大子数组是 [4,-1,2,1]，算法应当输出 6
注意：
此问题要求 计算子数组的最大和，而子数组一定是连续的，这就是为什么上面的示例 最大子数组中有个 -1，而不把除了负数之外的值全部加起来，为获取最大子数组和，那就得经过 -1
此问题与此前提到的 最长递增序列比较类似
俄罗斯套娃信封
有一个二维整数数组 envelopes ，其中 envelopes 中的每个值代表着一个信封，每个信封的宽度和高度以整数对 [ w, h ] 表示，当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样
计算 最多有多少个信封能组成一组 “俄罗斯套娃” 信封
比如输入
envelopes = [[5,4],[6,4],[6,7],[2,3]]，能组成最多套娃信封组是 [2,3] => [5,4] => [6,7]，算法应当输出 3
不同子序列
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
简单来说就是：从 s 字符串上 挑字符，求能匹配 t 字符串的次数是多少
比输入
s="beear"，t="bear，其中从s身上挑字符，能匹配t=bear的方式有两种，算法应当输出 2
总结
个人感觉动态规划难以理解的原因有这些🤧
- 结构庞杂，需要将问题划分成一个个子问题，每个子问题分别运算，先解决相对简单的子问题，再逐步解决大问题，最后求最优解
- 要充分结合问题 设计出动态规划解决方案(状态转移方程)是最困难的部分
- 如何去设计 DP Table，问题最简单的情况(base case)是什么，每个子问题能做出什么选择发生改变
动态规划 所带来的启示🤪
- 在问题可分解为彼此独立且离散的子问题时，在给定约束条件下，就能够使用动态规划来设计解决方案
- 每中动态规划方案背后都有着网格，如上面所展示的一系列图，每个格都是一个个子问题
- 动态规划先解决相对简单的子问题，再逐步解决大问题
- 可以先确定 最简单的情况 (base case) 和 最终答案在 DP 中的位置，再尝试找出 状态转移方程
动态规划思路流程
- 先设计出DP Table，并明确其含义
- 找到问题最简单(base case)的情况是什么
- 寻找设计出 状态转移方程
动态规划是一个难以理解算法概念，这是真的，但愿上述内容能够帮得上忙🥶
有个更简单的例子：斐波纳契数列 ，其用到的伪动态规划的解法不妨去看看
后记
动态规划是一个难以理解算法概念，但深入研究时会发现动态规划还是有点意思的，让人又爱又恨，为了研究什么是动态规划，以及如何去实现，我查阅大量的资料，花费大量时间学习，在此期间我十分感谢网上大佬们各种各样的文章，给我一定的启发，我决定写下这篇笔记分享给大家。
我是个不折不扣的新手，文章内容或许存在不足、错误，这里请大家谅解，比起博客我更喜欢称呼这为笔记。
此笔记会持续更新、改进（还未写完），要是有路过的大佬可以指出我的错误，我会感到高兴，十分感谢😋
参考资料
在攻克动态规划算法时，我十分感谢这些帮助过我的资料、书籍，可以说没有它们的帮助，我难以啃动 动态规划 这块硬骨头，再次感谢书写这些资料、书籍的作者们
在这里我把这些资料、书籍给列出来，欢迎大家去查看，书籍可以在京东上能够买到
- 题目出之力扣：
- 不同子序列 leetcode 115
- 维基百科中文版：
- 书籍：
- 图灵程序设计丛书 《算法图解》
这是一本很棒的算法入门书，推荐给大家 - labuladong大佬 著作 的 《labuladong 的算法小抄》
这是一本很厉害的书，十分推荐
- 图灵程序设计丛书 《算法图解》
由衷感谢💖
相关博客😏
为开发者提供学习成长、分享交流、生态实践、资源工具等服务，帮助开发者快速成长。
更多推荐
76
0- 0
已为社区贡献6条内容
所有评论(0)