一类典型动态规划问题解析Censored!一道简单问题分析由于gum,dog可以在dogum字样中同时出现，故有：分析分析分析时间复杂度回到原题考虑下面这样一颗单词树分析样例分析这样我们很容易写出状态转移方程BlocksSample算法分析定义状态设S(i,j,k)为(color[i],len[i]),(color[i+1],len[i+1])…(color[j-1],len[j-1])的连续同色整段以及在一系列消除操作后j后接了k个颜色为color[j]的方块(color[j],len[j]+k)的一个颜色序列.设f(i,j,k)表示消除S(i,j,k)这一个颜色序列可以得到的最大分值.算法分析动态规划转移方程f(i,j,k)=Max{f(i,j-1,0)+(len[j]+k)2,f(i,p,k+len[j])+f(p+1,j-1,0)}注意细节Robots举例分析状态转移方程总结附加问题1考虑这些机器人组成的路径继续分析于是我们的算法流程这样的：总结附加问题2分析Hotel先考虑夫妇这个限制考虑动态规划考虑优化Distributingtasks举例分析分析考虑动态规划考虑是被一些1*k的矩阵覆盖为什么可以这样做？总结