常见动态规划的解决思路
字符串输入的一般解决思路
- 选择suffix作为子问题
- 选择prefix作为子问题
- 使用子集substring
- 有时候单个的选择已经不够了，比如背包问题，不仅需要知道要选择哪个物件，来得到价值，同时也需要知道还剩多少容量，也就是需要"记住"更多的子问题，或者说子条件来处理问题
编辑距离
给定两个字串x和y,将x变成y所需要改变的字符的个数是多少？期间可以的操作是:
- 插入字符c 耗时O(1)
- 删除字符c 耗时O(1)
- 将c更新为c' 如果C和C'是相同的，耗时O(0)，其它不考虑
字串可以是非连续的。它等效于找两个字符串的最大公共字串，比如 HIEROGLYPHOLOGY 和 MICHAELANGELO 最大公共字串为 HELLO
动态规划思路
- 子问题：X的子串X[i:]和Y的子串Y[j:]
- 猜测：只有3中可能的方式，要么把X[i]替换成Y[i],要么删掉X[i],要么把Y[i]插入X
- 循环：
DP(i,j)=min(cost of replace X[i] to Y[j]+ DP(i+1,j+1)，cost of delete X[i]+DP(i+1,j)，cost of insert Y[j]+DP(i,j+1) )
子问题的耗时:O(1)
- 拓扑排序：三个方向由右下角向左下角开始执行
for i in 0,...,|x|:
for j in 0,...,|y|:
复制代码原始的问题:DP(0,0)，总的时间为:O(1)*O(|x||y|)
矩阵相乘在哪个部分加括号运算才能使得运算最优
假设有如下形式的矩阵做乘法
如果直接按照顺序来计算,先乘A.B，得到的结果再乘C
如果优先运算 B.C ，结果再乘A
可以看到第二种方式消耗的时间会更少。
思路
动态规划解决思路
如何使得词在段落中的位置分配合理，使得更美观
给定一个词的集合words,使用badness(i,j)表示使用的单词是words[i,j]
暴力解决方案
动态规划
按照标准的动态规划步骤来进行:
- 找到子问题：集合的后缀 words[i:]
假设找到了第一行的分隔点，那么接下来需要考虑的是第二行又该在哪儿开始换行呢？依次继续往下去查找，所以需要思考的子问题就是去掉第一行的词之后，剩下的那些单词
子问题的数量:n。只有n个单词，后缀的次数也就是这些
- 猜测：第二行从哪儿开始？
猜测的选择的数量：<=n-i=O(n)。每次选完了第一行，只需要在剩下的单词里面选
- 循环:
DP[i]=min(badness(i,j)+DP[j] for j in range(i+1,n+1))
定义问题为求DP(i)的最小值。当i=n的时候，是没有单词剩下的，花销是0。 假设第一次在第i个位置开始换行，第一行的计算发方式为 badness(i,j),剩下的需要解决的问题部分是从i+1开始的单词，也就是剩下部分的花销假设从j开始，它可能取得剩下部分的任意值，每个j的取值所需要的花销就是D(j),那么这两部分相加最小时，也就是最优的划分方式
循环部分耗时(每个子问题耗时):O(n)。j总共有n种选择，加法部分是常量
- 拓扑排序:i=n,n-1,...,0
- 检验原始问题是否解决：即DP(0)是否解决
使用一个指针parent来表明j中的最小值是那个，那么沿着parent指针，0->parent[0]->parent[parent[0]]一直到最后，即可得到最佳的划分方式
吉他放手指的问题
有一个吉他，在弹的时候，可以用任何一个手指来谈，那么如果给予一系列的音符notes，每个音符都需要用手(手指头取值 1,..,F)处理，每个手指去某个音符弹后需要移到另一个音符用一个手指去弹，假设描述这种移动使用d(p,f,q,g)表示花销，那如何去使得花销最小？
d(p,f,q,g):表示手指f移动到g，弹的音符从p到q
一般思考是：
- 子问题：notes[i:],即后面的音符怎么去弹
- 猜测：该用那个手指头来谈音符i
- 循环：可以选择任意一个手指头去弹新的音符，但是当从旧的音符切换到新的音符去弹的时候，无法知道该切换到那个手指： DP(i)=min(DP(i+1)+d(i,f,i+1,?) for f in 1,..F) 所以子问题"记住"的过少，需要增加考虑的情况。
正确思路为：
- 子问题：notes[i:],即后面的音符怎么去弹，同时该那个手指f去弹notes[i:]
- 猜测：使用手指g来谈notes[i+1]
- 循环: DP(i,f)=min(DP(i+1,g)+d(i,f,i+1,g) for g in 1,..F)
i表示note[i]的音符
- 拓扑排序
for i in reversed(range(n)): //所有的音符
for f in 1...F: //每个手指头都有可能来弹音符
复制代码最终去解决原始问题，DP(0,f),但是需要指定f,所以使用 min(DP(0,f) for f in 1,...,F)，即初始的时候应该选择那一个手指去谈第一个音符
这种场景即是要考虑更多的情况，来达到最优解