动态规划基本思想
动态规划的工作原理是先解决子问题，再逐步解决大问题。
用动态规划解决旅游规划问题
目前面对的问题是，有A、B、C、D、E五个地点想要去参观，每个地点的评分不同，花费的时间也不同，假设你有两天的时间，怎么样能够在两天内参观达到评分最多的参观路线呢？各地点的花费时间以及评分如下：
| 名胜 | 时间/天数 | 评分 |
|---|---|---|
| A | 0.5 | 7 |
| B | 0.5 | 6 |
| C | 1 | 9 |
| D | 2 | 9 |
| E | 0.5 | 8 |
动态规划可以看做是一个建立网格并且填写网格的过程，表格填好后问题也可解决。建立一个空白的网格如下：
| 0.5 | 1 | 1.5 | 2 | |
|---|---|---|---|---|
| A | ||||
| B | ||||
| C | ||||
| D | ||||
| E |
- 填写A行
这一行中，每一个网格只需要决定要不要去A地，填写当前网格可能的最高评分值，牢记目的是使评分最高，0.5代表只有0.5天时间，1代表有1天时间，以此类推，因此A行的网络填写如下，每个网格都选择去A地：
- 填写A行
A行网格评分.png
-
2.填写B行
B行填写时每个网格可选A.B两地，目的同样是选择评分更高的选项，准则如下，首先确定是否选择B，如果选择B，计算选B之后的空闲时间，并与空闲时间列的上一行最高评分值相加，作为这一网格的最高评分，若和大于上一行同列的评分则作为这一网格最终的评分，否则不选择B，继承上一行的评分。
B行网格评分.png
如B行第一列，假设选择B，则正好用完0.5天得到评分6，与上一行的7相比较小，因此，不选择B，继承上行的结果；第二列则为选择B后剩余0.5天，查找0.5天列的上一行，评分最高为7，故该网格的最高评分为7+6=13，超过上一行7，最终确定填写为13。
-
3.填写剩余行
每多一行，可选择的地点就多一个，填网格的法则如上，不在赘述，最终的网格如下：
由图可知最终选择ACE三地参观可获得最高的评分。
最终网格.png
动态规划的注意事项：
1.动态规划的结果不会随网格的行顺序而改变；
2.在动态规划时每个网格只有两种选择，是or否，没有选择商品的一部分这种选项；
3.动态规划的每个子问题都必须是离散独立的，不能依赖于其他子问题。
动态规划查找最长公共子串
动态规划要将某个指标最大化，最长子串指的是两个单词中相同字母最多的字符串，例如red和reg的最长公共子串是re，利用动态规划解决该问题单元格的值为共同字符串长度值，横纵坐标分别为两个单词，最终的结果为单元格中的最大值而不是最后一个单元格的值。
- 计算公式：
1.如果两个字母不同，值为0；
2.如果两个字母相同，值为左上角邻居的值加1；
举例，fish和fosh的最长公共子串的最长公共子串长度为2，是sh
最长公共子串.png
- python 代码实现
#动态规划解决最长公共子串问题
def findCommenstr(str1,str2):
cell = [[0 for x in range(len(str2))] for y in range(len(str1))]
max_ = 0
max_id = -1
for i in range(len(str1)):
for j in range(len(str2)):
if str1[i]==str2[i] and (i < 1 or j < 1): #确定第一行或者第一列的值
cell[i][j]=1
elif str1[i]==str2[j]: #如果相同，加上左上角的值
cell[i][j]=cell[i-1][j-1]+1
if cell[i][j] > max_:
max_ = cell[i][j] #获取最大值
max_id = i #获取行号
sub_str = []
for i in range(max_id-max_+1,max_id + 1):
sub_str.append(str1[i])
return sub_str,max_
a='fish'
b='fosh'
sub,str_len = findCommenstr(a,b)
print(''.join(sub),str_len)
动态规划查找最长公共子序列
最长公共子序列：两个读单词都有的序列包含的字母数，即将各个公共子串的长度相加。子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续
举例fish和fosh的最长公共子序列是fsh，长度为3。
最长公共子序列.png
-
计算公式
1.如果两个字母不同，就选择上方和左方邻居中较大的；
2.如果两个字母相同，就将当前单元格的值设置为左上方单元格的值加1。 -
得出公共子序列
通常的学习资料中只有如何计算出最长公共子序列长度，没有将子序列具体串得出，笔者通过自己的研究，r如有问题，还请指教，笔者认为得出子序列输出的步骤如下：
1.得到网格最大值的位置，将最大值对应的字符添加到子序列集合，
当该位置不是第一行或者第一列时，将该值与左上方的结果比较：
如果左上邻居小于当前值，将左上的邻居加入子序列集合；
否则，先将当前值pop出集合，再将左上邻居添加到子序列集合；
依次向网格左上方移动，直到遍历完网格的位置。
python实现代码如下：
# chapter 9 动态规划解决两个单词最长公共子序列问题
def findCommenstr(str1,str2):
cell = [[0 for x in range(len(str2))] for y in range(len(str1))]
max_ = 0
max_id = -1
flag = []
max_id_x =-1
max_id_y =-1
for i in range(len(str1)):
for j in range(len(str2)):
if str1[i]==str2[j] and (i<1 or j < 1): #确定第一行第一列的值
cell[i][j]=1
elif str1[i]==str2[j]: #如果相同，加上左上角的值
cell[i][j]=cell[i-1][j-1]+1
else:
cell[i][j]=max(cell[i-1][j],cell[i][j-1]) if i>0 else cell[i][j-1]
if cell[i][j] > max_:
max_ = cell[i][j] #获取最大值
max_id_x = i #获取行号
max_id_y = j
if max_id_x !=-1: #如果没有公共子序列则flag为[]
flag.append(str1[max_id_x])
while (max_id_x > 0 and max_id_y > 0): #如果有公共子序列，回溯确定公共子串
if cell[max_id_x-1][max_id_y-1] < cell[max_id_x][max_id_y] and cell[max_id_x-1][max_id_y-1]>0:
flag.append(str1[max_id_x-1])
elif cell[max_id_x-1][max_id_y-1] == cell[max_id_x][max_id_y] and cell[max_id_x-1][max_id_y-1] > 0:
flag.pop(-1)
flag.append('*-*') #分隔子串的标记
flag.append(str1[max_id_x-1]) #如果相等先把当前的拿出然后再添加左上角值
else: #如果当前表格已经为0，则结束
flag.reverse()
return flag,max_
max_id_x-=1
max_id_y-=1
flag.reverse()
return flag,max_
a='sish'
b='wosh'
s,str_len = findCommenstr(a,b)
print('Str1 is',a)
print('Str2 is',b)
print('The common string is ',s, ', And the length is ',str_len)
代码测试结果：
最长子序列代码测试结果.png
网友评论