4.4《算法图解》笔记——Chapter 9 dynamic programming

算法图解笔记——Chapter 9 dynamic programming
Author: Seven Zou
Email: [e-mail]
Language: Python2.7

---

9 动态规划

动态规划主要思想在于将问题分成小问题，并先着手解决这些小问题。

---

9.1 背包问题

再次回到昨天学到的背包问题。
解决方案一：
尝试各种可能的商品组合，并找出价值最高的组合。

但是在此方案下，运行速度将达到$O(2^n)$O(2n)。每增加一件商品，需要计算的集合都将指数形式增长。
解决方案二：
昨天了解近似求解的概念，针对这类问题就可以使用近似求解来寻找最优解，那么就可以使用动态规划算法，先解决子问题，再逐步解决大问题。类比此问题框架，那么就需要先解决小背包(子背包)问题，再逐步解决原来的问题。

假设每个动态规划算法都从一个网格开始，那么背包问题的网格为如下。

网格的各行为可选择的商品，各列为不同容量的背包。网格最初是空的，在填充满其中的每个单元格后，便能求出问题的答案。
-Row 1：吉他的重量刚好满足Column1 的1磅，那么可以将吉他的价格填入，相同操作，将吉他的价格填满第一行；在此行当前的最大价值为$1500
-Row 2：音响(4磅)，对Column {1-3} 重量不满足所有继续填入$1500，在Column 4(4磅)中可以满足则填入 $3000；此时最大价值更新为$3000
-Row 3：笔记本电脑(3磅)，与上述操作相同，可在Column3 填入 $2000。

商品	1	2	3	4
吉他	$1500	$1500	$1500	$1500
音响	$1500	$1500	$1500	$3000
笔记本电脑	$1500	$1500	$2000	——

那么针对(3,4)元素如何取值呢？针对4磅选取 可以有"音响$3000" 或 "笔记本$2000 + 吉他$1500"选择，这样就体现出了计算小空间的优势，可以凸显最大价值。显然选择“笔记本+吉他”。

商品	1	2	3	4
吉他	$1500	$1500	$1500	$1500
音响	$1500	$1500	$1500	$3000
笔记本电脑	$1500	$1500	$2000	$2000+$1500=$3500

在计算每个单元格的价值时，使用的公式都相同。
$cell[i][j]= \text{两者中较大的那个} \left\{ \begin{aligned} & cell[i-1][j] \\ & cell[i-1][j-\text{当前商品的重量}]\ \end{aligned} \right.$cell[i][j]=两者中较大的那个{​cell[i−1][j]cell[i−1][j−当前商品的重量] ​
如果再增加重量达到1磅的iphone($2000)，那么表格会变化为

商品	1	2	3	4
吉他	$1500	$1500	$1500	$1500
音响	$1500	$1500	$1500	$3000
笔记本电脑	$1500	$1500	$2000	$2000+$1500=$3500
iphone	$2000	$2000+$1500=$3500	$2000+$1500=$3500	$2000+$2000=$4000

各行的排列顺序对结果不产生影响。在此问题逐列填充网格也不会有任何影响。

旅游行程最优化

假设去伦敦度假，但假期两天的时间你想去游览的地方很多，那么需要做一个清单。

名胜	时间	评分
威斯敏斯特教堂	0.5Day	7
环球剧场	0.5Day	6
英国国家美术馆	1Day	9
大英博物馆	2Day	9
圣保罗大教堂	0.5Day	8

这也算背包问题，但约束条件是有限的时间。可以进行列表执行。

名胜	1/2	1	3/2	2
威斯敏斯特教堂	7	7	7	7
环球剧场	7	13	13	13
英国国家美术馆	7	13	16	22
大英博物馆	7	13	16	22
圣保罗大教堂	8	15	21	24

对于动态规划算法，应用仅当每个子问题都是独立、离散的(不依赖于其他子问题)。
对背包问题的最优解，也存在背包未装满的情况。

---

9.2 最长公共子串

假设你在管理网站dictionary.com。用户在该网站输入单词时，你需要给出其定义。如果用户拼错了，你必须猜测他原本要输入的是什么单词。比如Alex输入了hish，那他原本要输入fish还是vista呢？
应用动态规格算法我们继续使用网格，那么需要确定的是：
-单元格中的值是什么？
-如何将这个问题划分为子问题？
-网格的坐标轴是什么？
在动态规划中，你要将某个指标最大化，那么在这个例子中，你需要找出两个单词的最长子串。那么需要计算hish和fish、hish和vista的最长子串。单元格中的值通常就是要优化的值。在这个例子中，这有可能是一个数字：两个字符串都包含的最长子串的长度。那么如何划分这个问题，需要比较子串，不是比较hish和fish，而是先比较his和fis。每个单元格都将包含这两个子串的最长公共子串的长度。那么坐标轴可能是这两个单词。

	H	I	S	H
F
I
S
H

那么在填充单元格应该选用什么公式，但显然hish和fish最长公共子串是ish。对于这种情况，可以采用费曼算法(Feynman Algorithm)。步骤为：
-1.将问题写下来；
-2.好好思考；
-3.将答案写下来。

（emmmm…意外。）

那么就一步一步填入值，(1,1) = 0、(1,2)=0、(3,3)=2、(3,4)=0、(4,4)=3。最终网格结果为：

	H	I	S	H
F	0	0	0	0
I	0	1	0	0
S	0	0	2	0
H	0	0	0	3

针对每个单元格的值计算逻辑为：
伪代码为:

if word_a[i] == word_b[j]:		# 两个字母相同
	cell[i][j] = cell[i-1][j-1] + 1
else:							# 两个字母不同
	cell[i][j]=0

那么对于完整的hish和vista网格为：

	V	I	S	T	A
H	0	0	0	0	0
I	0	1	0	0	0
S	0	0	2	0	0
H	0	0	0	0	0

这里的答案与背包问题不同的是，这里的答案是网格中最大的数字，不一定位于最后的单元格中。那么回到问题本身，对比fish和vista之后，我们发现hish与fish的最长公共子串包含三个字母，那么猜测Alex很可能原本要输入的是fish。

最长公共子序列

假设Alex输入了fosh，那么他原本意图是fish还是fort呢？

	F	O	S	H
F	1	0	0	0
O	0	2	0	0
R	0	0	0	0
T	0	0	0	0
–	–	–	–	–
F	1	0	0	0
I	0	0	0	0
S	0	0	1	0
H	0	0	0	2

最长公共子串的长度相同，都包含两个字母，但fosh与fish更像。(有三个元素相同)。那么应该对比的是最长公共子序列：两个单词中都有的序列包含的字母数。那么创建下面网格来计算fish和fosh的最长公共子序列

	F	O	S	H
F	1	1	1	1
O	1	2	2	2
R	1	2	2	2
T	1	2	2	2
–	–	–	–	–
F	1	1	1	1
I	1	1	1	1
S	1	1	2	2
H	1	1	2	3

Fort的最长公共子序列为2，Fish的最长公共子序列为3。在填充时的逻辑为：

伪代码为：

if word_a[i] == word_[j]:							# 两个字母相同
	cell[i][j] = cell[i-1][j-1] + 1
else:
	cell[i][j] = max(cell[i-1][j], cell[i][j-1])	# 两个字母不同

Application：

• 生物学家根据最长公共序列来确定DNA链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
• git diff指令用来指出两个文件的差异，也是使用动态规划实现。
• 字符串的相似程度。编辑距离(levenshtein distance)指出了两个字符串的相似程度，也是使用动态规划计算得到的。边际距离算法的用途很多，从拼写检查到判断用户上传的资料是否时盗版。
• Microsoft Word等具有断字功能的app，他们确定在什么地方断字以确保行长一致，也是使用动态规划。

---

需要在给定约束条件下优化某种指标时，动态规划很有用。
问题可分解为离散子问题，可使用动态规划。
每种动态规划解决方案都涉及网格。
单元格中的值通常就是你要优化的值。
每个单元格都是一个子问题，因此需要考虑如何将问题分成子问题。
没有通用的计算动态规划解决方案的公式。

Reference

[美]Aditya Bhargava/袁国忠, 算法图解, 北京：人民邮电出版社, 2017.3.

---

附个人Github地址: https://github.com/shiqi0404/Algorithm_Diagram，其中包括笔记、Code还有书本pdf版。