LeetCode 651 4 Keys Keyboard

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2020-03-11 16:57:57
    编辑于：2022-02-20 10:28:50
    浏览量：1456

Link

第一种思路

状态：首先有剩余的按键次数，其次是缓冲区中的字符数以及屏幕上已有的字符数。

选择：4 种按键即 4 种选择。

注意：该思路复杂度太高 > O(N^3)。

第二种思路

状态：经过分析，最优操作只有两种情况，当 N 比较小时，全部按 A，否则是前面全按 A，后面为选择-复制，粘贴*n，也即每次选择复制后必跟着 n 次粘贴操作（n>0）。我们设前面按的 A 的个数为 i，总操作数为 j，则 dp(i,j) 表示该情况下 A 的最大量。

选择：选择-复制 or 粘贴。

总结

动态规划问题本质上为暴力枚举 + 剪枝。第二种思路减去了大量在后期选择 A 的决策分支，从而降低算法的时间复杂度至 O(n^2)。

Links: LeetCode-651-4-Keys-Keyboard