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

[utterances-bot]

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

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

[deepbreath373]

我就是CV程序员了XD

[fornobugworld]

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

[861130245]

前排提示会员题

[861130245]

很巧妙的第二种解法

[lan-dian]

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

[marcmk6]

+1
如果第n个操作注定是ctrl-V比A更好，直觉上应该最晚ctrl-A, ctrl-C才能最大ctrl-V的效果，也就是n-2时ctrl-A，n-1时ctrl-C。
但最优解居然是在中间某个地方选择复制后就一直按粘贴，按上面的直觉来想破脑袋也想不出来😂

[Carry955]

在极端的情况下，N很大，如果前面一直按A，直到最后才C-A, C-C, C-V一次，那就大致相当于每次增加3个A。而如果在A到第三个后就C-A, C-C，后面一直C-V，那就是每次增加3个A。

[lan-dian]

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

[xxrz]

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

[EyeDroplyq]

其实你可以理解为此时是第一次操作

[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]

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

[mengbingrock]

是的，官方题解最后一种解法。

[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那里就可以。以上是个人理解，如有错误，欢迎指出。

[chenxiiang]

j-2开始ca，dp[j-2]表示的是开始复制的时候已经有的A的个数

[RayL01]

作者这篇文章的解释写得不是很好

[Link-GZJ]

说的对，顶一个。dp[j-2]是最优值的话，不会是CA

[Velliy]

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

[yonggui-yan]

打卡打卡

dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));

[Goolloo]

关于简化Ctrl+V的次数

f(i) = max(i, f(i-3)*2, f(i-4)*3, f(i-5)*4, f(i-6)*5, f(i-7)*6, f(i-8)*7, f(i-9)*10, f(i-10)*11, ...)

Because f(i) is optimal max at i^th place, so f(i) >= 1

f(i-3) = max(i-3, f((i-3)-3)*2, f((i-3)-4)*3, f((i-3)-5)*4, f((i-3)-6)*5, f((i-3)-7)*6...
       >= f(i-6) * 2, f(i-7) * 3, f(i-8) * 4, f(i-9) * 5, f(i-10) * 6,

so
f(i-3)*2 >= f(i-6) * 4, f(i-7) * 6, f(i-8) * 8, f(i-9) * 10, f(i-10) * 12,

so in f(i) = max(i, f(i-3)*2, f(i-4)*3, f(i-5)*4, f(i-6)*5, f(i-7)*6, f(i-8)*7, f(i-9)*10, f(i-10)*11, ...)
we can ignore all of f(i-7)*6, f(i-8)*7, f(i-9)*10, f(i-10)*11, ...
because they are no larger than f(i-3)*2

so we can simplify f(i) to
f(i) = max(i, f(i-3)*2, f(i-4)*3, f(i-5)*4, f(i-6)*5)

[fakeyanss]

刚才说了，最优的操作序列一定是 C-A C-C 接着若干 C-V，所以我们用一个变量 j 作为若干 C-V 的起点

for (int j = 2; j < i; j++) {
            // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
            // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
            dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
}

对这一段的理解：

最优的结果，可以是

C-A C-C C-V C-V C-V C-V C-V C-V

也可以是

C-A C-C C-V C-V C-A C-C C-V C-V

一开始觉得后者可能是更优的结果，感觉作者的说法有问题。

后来想明白，这两种情况，都在这个 dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1)); 的比较里计算过了

[reozong]

是的，我似懂又非完全懂。

[okoldk]

大佬们这是我的理解，如不对烦请指正。
大致有以下两种可能：

1. A,A..CA,CC,CV,CV,CV,CV,CV..
2. A,A..CA,CC,CV,CV,CA,CC,CV..
   观察知道一定存在最后一次 CA-CC-CV，使结果最大化，大致如下：
   A,A..(不管打了A还是CV还是CA-CC-CV)..CA,CC,CV,(继续0次或者若干次CV)
   遍历所有可能，找到那一次CV位置

[Roger-jc-Lu]

我在没看第二种方法之前自己改了一种第一种笨办法的剪枝，目前可以通过所有case，用原来的做选择去思考，比较intuitive
主要是因为这个题前几个case比较好推导，也能推出在出现3~4个A之后我们是不可能再去按单独的A了，所以这个选择在6个以上按键机会中直接被整个剪枝砍掉，其他剩下的剪枝想法在comment
in python：

def maxA(self, n: int) -> int:
        # 比较容易推导在n为7之前最效率的方法就是按6次A或者3次A然后三键套
        # 得出的结果均为6
        if n <= 6:
            return n

        memo = {}

        # dp的param现在是一个会放进memo的key
        def dp(key):
            if key in memo:
                return memo[key]

            n, a_num, copy = key[0], key[1], key[2]

            # base case
            if n <= 0:
                memo[key] = a_num
                return a_num

            # 如果屏幕上的A和cache里的一样多
            # 说明我们才进行了 C-A, C-C, 下一步必定是C-V, 其实只有一种选择
            if a_num == copy:
                res = dp((n - 1, a_num + copy, copy))
                memo[(n - 1, a_num + copy, copy)] = res
                return res

            # 比较我们是继续C-V 还是重新C-A, C-C 收益高
            else:
                res_paste = dp((n - 1, a_num + copy, copy))     # C-V
                res_copy = dp((n - 2, a_num, a_num))       # C-A C-C
                if res_paste > res_copy:
                    memo[(n - 1, a_num + copy, copy)] = res_paste
                    return res_paste
                else:
                    memo[(n - 2, a_num, a_num)] = res_copy
                    return res_copy
        
        # dp的调用，比较(n - 6), 即6键之后的两种最优情况优劣
        # 第一种是6个A上屏，cache里存了3个A (3次A然后三键套)
        # 第二种是4个A上屏，cache里存了4个A (4次A然后copy所有A)
        return max(dp((n - 6, 6, 3)), dp((n - 6, 4, 4)))

[qin-ny]

java版dp版本

public int maxA(int n) {
// cache[i]定义是最多操作i次的时候可以显示最多的A数量
int[] cache = new int[n+1];

    // base case
    cache[0] = 0;

    for (int i=1;i<=n;i++) {
        // 此处选择A按键
        cache[i] = cache[i-1]+1;

        // 此处选择进行Ctrl-A、Ctrl-C、Ctrl-V
        // 因为可以推测出，要进行Ctrl-A就肯定是后面跟Ctrl-C再至少跟一个Ctrl-V才能显示尽可能多的A
        // 不然Ctrl-A、Ctrl-C、Ctrl-V这三个操作中间添加任何的Ctrl-A、Ctrl-C都是多余操作
        // Ctrl-A、Ctrl-C、Ctrl-V这三个操作中间添加任何的A都可以移动到Ctrl-A之前让结果更大

        // 初始从Ctrl-A、Ctrl-C后面跟一个Ctrl-V开始计算，倍数是算上复制之前的屏幕A数量，是2
        int index = i-3, mul=2;
        while (index >= 0) {
            cache[i] = Math.max(cache[i], cache[index]*mul);
            // 每次增加一个Ctrl-V，倍数加1
            index--;
            mul++;
        }
    }
    return cache[n];
}

[EyeDroplyq]

打卡，附上详细注解的Java代码，希望有个老哥可以帮我测一下，我没有plus会员

    public int maxA(int N){
        //dp数组的定义，当你进行到第i次操作的时候你屏幕中最多有dp[i]个A，这里什么是N+1呢，因为整体右移一位，i=0无意义
        int[] dp=new int[N+1];
        //i=0的时候无意义，所以先赋一个初值
        dp[0]=0;
        //base case：第一次操作的时候，屏幕中A要是最多的话，只能是输入了一个A。
        dp[1]=1;
        //做选择，我们的选择要保证屏幕中A最多，所以有两种情况
        //1.我们一直按A
        //2.我们先按A，然后在合适的地方按C-A,C-C,然后一直按C-V，如果是这种情况的话，我们要记录第一次按C-V的位置
        for (int i =2 ; i <=N ; i++) {
            dp[i]=dp[i-1]+1;//如果我们选择按A的话，就是前面的屏幕中A的个数然后加1即可
            for (int j = 2; j <i ; j++) {
                //选择第二种方案的话，我们用j来记录第一次按C-V的地方,我们屏幕中的最多A的数量就是
                // 从j到i一直按C-V，那么dp[j]的时候的屏幕上的A的个数乘以（i-j+1）就是屏幕中最大的A的数量
                dp[i]=Math.max(dp[i],dp[i-2]*(i-j+1));
            }
        }
        //最后返回的结果就是全部按完的时候的结果
        return dp[N-1];
    }

[EyeDroplyq]

！！！！！上面的算法是错误的！！！！

附上新的代码，并且给大家个福利，可以去这个地方测试代码，四键键盘

    public int maxA(int N){
        //dp数组的定义，当你进行到第i次操作的时候你屏幕中最多有dp[i]个A，这里什么是N+1呢，因为整体右移一位，i=0无意义
        int[] dp=new int[N+1];
        //i=0的时候无意义，所以先赋一个初值
        dp[0]=0;
        //base case：第一次操作的时候，屏幕中A要是最多的话，只能是输入了一个A。
        dp[1]=1;
        //做选择，我们的选择要保证屏幕中A最多，所以有两种情况
        //1.我们一直按A
        //2.我们先按A，然后在合适的地方按C-A,C-C,然后一直按C-V，如果是这种情况的话，我们要记录第一次按C-V的位置
        //下面的选择就会从第一种方案和第二种方案中选择屏幕中A最多的那个情况
        for (int i =2 ; i <=N ; i++) {
            dp[i]=dp[i-1]+1;//如果我们选择按A的话，就是前面的屏幕中A的个数然后加1即可
            for (int j = 2; j <i ; j++) {
                //选择第二种方案的话，我们用j来记录第一次按C-V的地方,我们屏幕中的最多A的数量就是
                // 从j到i一直按C-V，那么dp[j]的时候的屏幕上的A的个数乘以（i-j+1）就是屏幕中最大的A的数量
                dp[i]=Math.max(dp[i],dp[j-2]*(i-j+1));
            }
        }
        //最后返回的结果就是全部按完的时候的结果
        return dp[N];
    }

[zhangmuwuge]

内部循环这样会不会更好呢
for (int j = 3; j <i ; j++) {
dp[i]=Math.max(dp[i],dp[j-3]*(i-j+1)+dp[j-3]);

}
为什么是3呢,因为定义的是 j是粘贴的位置,那么这个粘贴的应该3步之前的dp[j-3]位置的A的数量---- 而i到j都是cv的话,那么总共是j-i+1个cv,所以从j开始cv 复制的A的数量是 dp[j-3](i-j+1),又因为得加上原本的A dp[j-3] ,所以总数就是 dp[j-3](i-j+1)+dp[j-3]

[zhangmuwuge]

来个大佬分析一下吧

[faradawn]

我花了好久才意识到，最优的方法并不是先打一些A，然后一直Ctrl-V到结束！例如，给定11步，最好的方法是

a, a, a, Ctrl A + C, Ctrl V, Ctrl V, Ctrl A + C, Ctrl V, Ctrl V。

我画了一张图来解释（英文 Leetcode）：https://leetcode.com/problems/4-keys-keyboard/solutions/3737545/the-optimal-way-is-not-typing-a-s-at-first-and-then-ctrl-v-to-the-end-with-drawing/