本篇将介绍动态规划相关知识。
一、简介
动态规划（Dynamic Programming，简称DP）。
它的核心思想是把一个复杂的大问题拆成若干个子问题，通过解决子问题来逐步解决大问题。
注意：使用动态规划思想有个前提：当且仅当每个子问题都是离散的（即每个子问题都不依赖于其他子问题时），才能使用动态规划。
二、动态规划之“0-1背包问题”
现在有这么一个场景，
“你”是一名“小偷”，你带了个包去“偷东西”，。
条件1：每个商品只有一个，要么拿，要么不拿。（0-1背包问题）
条件2：你最多拿得动4kg的东西。（固定大小，可不装满）
| 商品 | 价格 | 重量 |
|---|---|---|
| 商品A | 3000元 | 4kg |
| 商品B | 2000元 | 3kg |
| 商品C | 1500元 | 1kg |
| 商品D | 2000元 | 1kg |
在有限的重量条件下，如何“偷”，赚的钱最多？
方案一：简单算法（可行，不推荐）
暴力枚举出所有商品的排列组合，
舍去所有超出重量要求的组合，
从中挑一个最大的。
可行，但是太慢了，每多一件商品都会多2倍的组合。
方案测评：时间复杂度 O(2n)，超级超级慢，不推荐。
方案二：贪心算法（不可行）
用上篇介绍的贪心算法计算。
通过某个贪心策略（拿最贵的、拿性价比最高的商品）来得出近似解。
方案测评：这种方案接近最优解，是近似解，但不一定是最优解，故不可行。
方案三：动态规划（可行，推荐）
- 原理：先解决子背包最优，再解决大背包最优。
先绘制出一张表格，一会我们一列一列慢慢填。（PS：体会动态规划的算法过程）
表格：（实际上对应了一个二维数组）
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | ||||
| 商品B | ||||
| 商品C | ||||
| 商品D |
先解读一下这个表格，
行：代表了商品行（对应i），
列：代表了重量列（对应j），
格：代表当前的已有的商品、已有重量下所能拿的最大价值。
好了，下面我们开始一列一列的填：
第一行，只有商品A（价值：3000，重量：4kg）
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | / | |||
| 商品B | ||||
| 商品C | ||||
| 商品D |
第二行，有商品A（价值：3000，重量：4kg）与商品B（价值：2000，重量：3kg）
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | / | |||
| 商品B | / | |||
| 商品C | ||||
| 商品D |
第三行，有商品A（价值：3000，重量：4kg）、商品B（价值：2000，重量：3kg）商品C（价值：1500，重量：1kg）
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | / | |||
| 商品B | / | |||
| 商品C | 1500 | |||
| 商品D |
第四行，有商品A（价值：3000，重量：4kg）、商品B（价值：2000，重量：3kg）、商品C（价值：1500，重量：1kg）、商品D（价值：2000，重量：1kg）
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | / | |||
| 商品B | / | |||
| 商品C | 1500 | |||
| 商品D | 2000 |
大家有没有发现，这里填写每个表格时的算法可表示为：
对应行的商品的重量超过当前子背包的重量，就取上一行单元格的值，
商品的重量能装下当前子背包，则取下面两者的较大值：
- 上一个单元格的值（
cell[i-1][j]）- 当前商品的价值 + 剩余空间的价值（
cell[i-1][j-当前商品的重量所对应的列号]）
下面填第二列：
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | / | / | ||
| 商品B | / | / | ||
| 商品C | 1500 | 1500 | ||
| 商品D | 2000 | 3500 |
第三列：
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | / | / | / | |
| 商品B | / | / | 2000 | |
| 商品C | 1500 | 1500 | 2000 | |
| 商品D | 2000 | 3500 | 3500 |
第四列：
| 商品\ 子背包最大重量 | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| 商品A | / | / | / | 3000 |
| 商品B | / | / | 2000 | 3000 |
| 商品C | 1500 | 1500 | 2000 | 3500 |
| 商品D | 2000 | 3500 | 3500 | 4000 |
于此反复判断即可，这样每个单元格都是最优解，通过解决子问题，推导出最终最优解。
这就是动态规划，是不是很简单呢？
转换成Python代码：
def package_dp(a, b, flag, n):
c = [[0 for i in range(n)] for j in range(n)]
for j in range(n):
c[0][j] = 0
for i in range(n):
c[i][0] = 0
for j in range(n):
if b[i]>flag[j]:
c[i][j] = c[i-1][j]
else:
temp1 = a[i] + c[i-1][j-b[i]]
temp2 = c[i-1][j]
c[i][j] = max(temp1,temp2)
print c[i][j]
print ("")
return c
price = [0, 3000, 2000, 1500, 2000]
weight = [0, 4, 3, 1, 1]
flag = [0, 1, 2, 3, 4]
package_dp(price, weight, flag, 5)
三、细节问题
-
子背包拆分问题：按照 所有商品 的最大公约数（也有可能存在小数）去拆子背包。
让所有的商品都能被刚好装下。 -
通过子背包的最优解 => 推导出 => 全背包的最优解。
这个过程的思想，就是DP思想（动态规划的核心思想）
四、动态规划的应用场景
本文举了背包与矩阵连乘的例子，其实思路都是一样的。
只是应用场景不同，常见的应用场景有以下几个：
- 0-1背包问题（ ✔️）
- 矩阵连乘法（ ✔️）
- 硬币找零
- 字符串相似度
- 最长公共子序列
- 最长递增子序列
- 最大连续子序列和/积
- 有代价的最短路径
- 瓷砖覆盖（状态压缩DP）
- 工作量划分
参考资料：
小编微信：可加并拉入《QiShare技术交流群》。
关注我们的途径有：
QiShare(简书)
QiShare(掘金)
QiShare(知乎)
QiShare(GitHub)
QiShare(CocoaChina)
QiShare(StackOverflow)
QiShare(微信公众号)
推荐文章：
Dart基础（一）
Dart基础（二）
Dart基础（三）
Dart基础（四）
iOS 短信验证码倒计时按钮
iOS 环境变量配置
iOS 中处理定时任务的常用方法
奇舞周刊
网友评论