经典动态规划：四键键盘 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：经典动态规划：四键键盘

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

我就是CV程序员了XD

[fornobugworld]

这个递推公式跟别的递归都不一样，每一步都重新计算前面所有可能，复杂度O（n）的状态转移第一次见，算是奇葩题吧。。

[kevinlainyc]

dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1)); 这里为什么是 i-j+1?

[kevinlainyc]

忘了算上已经复制在屏幕上的dp[j-2]个A

[861130245]

前排提示会员题

[861130245]

很巧妙的第二种解法

[lan-dian]

为什么是C-A,C-C之后一直C-V呢，如果再一定数量的时候，再拷贝一次，底数应该就翻倍了，效果后续肯定能超过一直C-V，如果在txt里面凑字数的话，肯定能感受出来的。

[lan-dian]

一旦我们C-A，C-C了一次之后，就没有按下A的必要了，因为C-V肯定比A多，我们考虑的肯定是什么时候，采用C-A，C-C增倍

[xxrz]

请教一下，第二种解法的状态定义是不是有一些问题？如果dp[i]定义为剩下为i个操作数，屏幕上A的数量。那最后的结果应该是dp[0]才对吧

[ztc0323]

我想知道图中 j = 5 的地方是 3 还是 6，j=5的地方是C-V操作，应该是6，推到后面就不对了

[Yijia0106]

我的理解是 当剩余操作数n<=6的时候 直接打A的数量是最优的，因为先打3个A然后CACCCV一套也是6步产生6个A，在之后的话就要考虑继续CV还是重来一遍CACCCV；当cv粘贴的数量<CACCCV重新复制粘贴的数量-3时 可以选择后者

[lhcezx]

确实看懂了 也能自己写出来，但是这种思路真的很巧妙，感觉没做过的话面试应该在有限时间内想不出来的。

感觉j可以从3开始一直到i，毕竟如果j = 2实际就是屏幕上没有A就ctrlA ctrlC，相当于什么也没复制

[chengrenfeng]

我感觉这题应该有一种数学办法可以直接算出来。

[Velliy]

for (int j = 2; j < i; j++) 个人感觉这里j可以等于i吧，就相当于第i次操作可以复制，相应的dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 2)); 不然的话，第j次操作是复制，为啥不能等于i？当前第i次操作就只能是按A了，虽然i+1的时候j还会遍历到当前的i，但是最后i=N的时候j最大N-1，那最后一次操作不就只能按A了么？这里也没讲明白啊

[Velliy]

我自己dubug悟了，“所以我们用一个变量 j 作为若干 C-V 的起点。那么 j 之前的 2 个操作就应该是 C-A C-C 了”这里表述是有问题的，j那次操作不是CV而是CC，j+1才是CV的起点，j之前也就是j-1那一次的操作是CA，j-2是什么操作不知道，反正dp[j-2]是j-2次操作下的最优值，因为j-1是CA，j是CC，所以i-j就是j之后包括i在内的粘贴次数，是对dp[j-2]的粘贴，再加上dp[j-2]本身，所以dp[i]可以为dp[j - 2] * (i - j + 1)。另外最后一个图画的也不准确，根据定义：dp[i] 表示 i 次操作后最多能显示多少个 A，那么图中下标为4的地方就是第四次操作也就是CA，所以直接把CA画在下标4那里就可以。以上是个人理解，如有错误，欢迎指出。

[Velliy]

哦另外，j是CC，i是CV，所以“for (int j = 2; j < i; j++)” 这里j<i是解释的通的，(i - j + 1)已经把i是粘贴算进去了。