给定两个字串x和y,将x变成y所需要改变的字符的个数是多少?期间可以的操作是:
字串可以是非连续的。它等效于找两个字符串的最大公共字串,比如 HIEROGLYPHOLOGY 和 MICHAELANGELO 最大公共字串为 HELLO
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]
按照标准的动态规划步骤来进行:
假设找到了第一行的分隔点,那么接下来需要考虑的是第二行又该在哪儿开始换行呢?依次继续往下去查找,所以需要思考的子问题就是去掉第一行的词之后,剩下的那些单词
子问题的数量: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种选择,加法部分是常量
使用一个指针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
一般思考是:
正确思路为:
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),即初始的时候应该选择那一个手指去谈第一个音符
这种场景即是要考虑更多的情况,来达到最优解