仅用于记录学习，欢迎批评指正，大神勿喷
系列文章目录
《算法图解》总结第 1 章：二分查找、大O表示法；
《算法图解》总结第 2 章：数组和链表，选择排序；
《算法图解》总结第 3 章：while循环、递归、栈；
《算法图解》总结第 4 章：分而治之、快速排序；
《算法图解》总结第 5 章：散列表；
《算法图解》总结第 6 章：广度优先搜索；
《算法图解》总结第 7 章：狄克斯特拉算法；
《算法图解》总结第 8 章：贪婪算法
《算法图解》总结第 9 章：动态规划
《算法图解》总结第 10 章：K最近邻算法
《算法图解》总结第 11 章：十种算法简介
文章目录
- 系列文章目录
- 动态规划
-
- 原理
- 启示
- 动态规划设计方案小贴士
- 补充知识
- 应用案例一：最长公共子串(LCS)
- 应用案例二：最长公共子序列
动态规划
动态规划是解决棘手问题的一种方法，它将问题分解成小问题，并先着手解决这些小问题。
原理
在本书中，运用动态规划解决了两个问题：背包问题和旅游行程最优化问题，现在就以旅游行程最优化的问题为例，介绍一下动态规划的原理。
旅游行程最优化
案例：假设你要去伦敦度假，假期两天，但是想游览的地方很多，列出以下清单:
根据清单，决定该游览哪些名胜。
案例分析：用动态规划的方法来分析：
行是对名胜的限制，列是对时间的限制。
第一行：名胜只有威斯敏斯特教堂，游览时间需0.5天，即不管时间是0.5天，1天，1.5天还是2天均只能游览威斯敏斯特教堂，总分值为7。
第二行：名胜里添加了环球剧场，它的游览时间也需0.5天，即名胜有威斯敏斯特教堂和环球剧场，当游览时间只有0.5天时，只能选择其一去游览，因为7>6，所以选择游览威斯敏斯特教堂，总分值为7，当游览时间为1天时，两个名胜游览时间加起来刚好是一天，因此都可以去游览，总分值为7+6=13，当游览时间大于1天时，由于名胜的限制也只能游览这两个地方，总分值依然为13。
其他三行分析方法雷同。
从整体来看，在没有S之前游览1.5天最优计划是W+N，总分值为7+9=16分，因为要游览两天还差0.5天，到达S后，剩余名胜里游览时间是0.5天的名胜是G和S，因为G的评分为6，S的评分为8，6<8,所以剩余的0.5天选择去S，即最优的游览计划是W+N+S，这就运用了将大问题转化为小问题的方法，即动态规划。
注意事项：
（1）再增加一个新的名胜，最大价值可能发生变化。
（2）沿着一列往下走时，最大价值不可能比以前低，因为每次迭代时，存储的都是当前的最大价值。
（3）行的排列顺序发生变化时最终的答案是没有变化的，即各行的排列顺序无关紧要。
（4）一般都是选择逐行填充网格，逐列填充网格可能会对问题产生影响，也可能不会产生影响。
（5）再增加一个新的名胜，游览时间仅需0.25天，因为比最小的间隔0.5天要小，此时要调整网格的间隔，调整间隔至0.25天。
（6）动态规划能处理相互依赖的情况吗？答案是否定的！比如我们游览某个名胜需要1天，那我们可不可以只游览0.5天就返回呢？现实中是可以的，但是在动态规划中这种情况是不允许的，要么选择游览就游览完，即游览1天，要么不游览，没法处理游览一半的情况。仅当每个子问题都是离散的，即不依赖其他子问题时，动态规划才管用。
（7）计算最终的解时不会涉及两个以上的子问题，因为根据动态规划算法的设计，最终只需合并两个子问题。
（8）最优解可能导致背包没装满，意为时间还没完全到两天，已经去完了最佳的游览地点。
启示
从动态规划问题中，我们得到的启示是：
（1）动态规划可帮助我们在给定约束条件下找到最优解。在背包问题中，必须在背包容量给定的情况下，偷到价值最高的商品；在旅行最优化问题中，必须在给定时间内，选择最优的名胜去游览；
（2）在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
动态规划设计方案小贴士
（1）每种动态规划解决方案都涉及网格；
（2）单元格中的值通常就是要优化的值；
（3）每个单元格都是一个子问题，因此我们应考虑如何将问题分成子问题，有助于找出网格的坐标轴。
补充知识
子串：原始字符串的一个连续子集
子序列：原始字符串的一个子集
range（）函数使用举例：
输出结果：
应用案例一：最长公共子串(LCS)
案例：用户在某网站输入单词时我们需给出定义，若用户拼错了，我们必须猜测他原本输入的是什么单词。假设Alex输入了hish，那他原本要输入的是fish还是vista呢？
案例分析：
LCS问题解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0。然后求出对角线最长的1的序列和，其对应的位置就是最长匹配子串的位置。以此例演示如下：
算法实现:
def find_lcsubstr(s1, s2):
# 生成0矩阵，为方便后续计算，比字符串长度多了一行一列，原因：
# 当i恰好为最后一个字符时，如果不多加一行一列，i+1和j+1均超出限制，导致无法继续计算
m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]
#最长匹配的长度
mmax=0
#最长匹配对应在s1中的最后一位
p=0
# 开始匹配
for i in range(len(s1)):
for j in range(len(s2)):
# 如果两个字母相同，就将当前单元格的值设置为左上方单元格的值加1
#若两个字母不同，当前单元格的值为0，与假设的相同，此处省略
if s1[i]==s2[j]:
# m是矩阵，其中m[i][j]指的是m矩阵的第i行第i列个元素
m[i+1][j+1]=m[i][j]+1
# 在两个字母相同的情况下更新最长匹配长度
if m[i+1][j+1]>mmax:
mmax=m[i+1][j+1]
# 之所以要令p=i+1是因为输出字符串s1[p-mmax:p]的时候输出的是p-mmax至p的前一位。
p=i+1
#返回最长子串及其长度
return s1[p-mmax:p],mmax
测试1：
输出结果：
演示算法执行过程：
测试2：
输出结果：
总结：因为3>2，所以用户原本要输入最可能是fish。
应用案例二：最长公共子序列
案例：假设Alex不小心输入了fosh，那他原本想输入的是fish还是fort呢？
案例分析：
遇到此类型题时，我们想到了刚才学到的最长公共子串的问题，首先我们先试一下，看一下结果：
print(find_lcsubstr('fosh','fish'))
print(find_lcsubstr('fosh','fort'))
输出结果：
('sh', 2)
('fo', 2)
因为这两组例子的最长公共子串的长度均为2，无法用其判断fosh和fish还是fort更像一些，那么是否还有其他方法解决此问题呢？我们想到了最长公共子序列算法。
子串要求字符必须是连续的，但是子序列就不是这样。最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。
解法就是用动态回归的思想，一个矩阵记录两个字符串中匹配情况，若是匹配则为左上方的值加1，否则为左方和上方的最大值。一个矩阵记录转移方向，然后根据转移方向，回溯找到最长子序列。
以此题为例，介绍一下最长公共子序列算法填充网格的过程：
算法实现：
import numpy
def find_lcseque(s1, s2):
# 生成字符串长度加1的0矩阵，m用来保存对应位置匹配的结果
m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]
# d用来记录转移方向
d = [ [ None for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]
# 开始匹配
for p1 in range(len(s1)):
for p2 in range(len(s2)):
# 如果两个字母相同，则该位置的值为左上方的值加1
if s1[p1] == s2[p2]:
m[p1+1][p2+1] = m[p1][p2]+1
d[p1+1][p2+1] = 'ok'
# 左值大于上值，则该位置的值为左值，并标记回溯时的方向为left
elif m[p1+1][p2] > m[p1][p2+1]:
m[p1+1][p2+1] = m[p1+1][p2]
d[p1+1][p2+1] = 'left'
# 上值大于左值，则该位置的值为上值，并标记方向up
else:
m[p1+1][p2+1] = m[p1][p2+1]
d[p1+1][p2+1] = 'up'
print numpy.array(d)
# 定义p1和p2的大小
(p1, p2) = (len(s1), len(s2))
s = []
# 注意是从p1和p2的最大值开始循环，转移方向为None时停止循环
while m[p1][p2]:
c = d[p1][p2]
# 匹配成功，插入该字符，并向左上角找下一个
if c == 'ok':
s.append(s1[p1-1])
p1-=1
p2-=1
# 根据标记，向左找下一个
if c =='left':
p2 -= 1
# 根据标记，向上找下一个
if c == 'up':
p1 -= 1
# 回溯，翻转s
s.reverse()
# 输出s的长度
print(len(s))
# ＂＂.join() 代表将括号里面的元素拼接成一个新的字符串
return ''.join(s)
测试：
print(find_lcseque('fosh','fish'))
print(find_lcseque('fosh','fort'))
输出结果：
[[None None None None None]
[None 'ok' 'left' 'left' 'left']
[None 'up' 'up' 'up' 'up']
[None 'up' 'up' 'ok' 'left']
[None 'up' 'up' 'up' 'ok']]
3
fsh
[[None None None None None]
[None 'ok' 'left' 'left' 'left']
[None 'up' 'ok' 'left' 'left']
[None 'up' 'up' 'up' 'up']
[None 'up' 'up' 'up' 'up']]
2
fo
总结：通过最长公共子序列可以看出，fosh和fish一致的字符串长度为3，fosh和fort一致的字符串长度为2，所以用户原本输入的最可能是fish。