动态规划四键与两键键盘

阅读量：

650. 只有两个键的键盘

题目描述-四键键盘

在这里插入图片描述

解题思路

状态转移：

第一个状态代表剩余的操作次数，在这里用n来表示；
第二个状态记录屏幕当前显示的字符A的数量，则通过a_num来进行量化；
第三个状态表示剪切板中存储的字符A的数量，则由copy来反映。

base case：当剩余次数 n 为 0 时， a_num就是我们想要的答案。

复制代码

    dp(n - 1, a_num + 1, copy), # A
    解释： 按下 A 键， 屏幕上加⼀个字符
    同时消耗 1 个操作数
    
    dp(n - 1, a_num + copy, copy), # C-V
    解释： 按下 C-V 粘贴， 剪切板中的字符加⼊屏幕
    同时消耗 1 个操作数
    
    dp(n - 2, a_num, a_num) # C-A C-C
    解释： 全选和复制必然是联合使⽤的，
    剪切板中 A 的

全部评论 (0)

还没有任何评论哟~