JustSong Archive Link About
Projects
Categories
Others

LeetCode 651 4 Keys Keyboard

Tag: LeetCode 动态规划 Posted on 2020-03-11 16:57:57 Edited on 2020-06-07 11:17:50 Views: 147

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)。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/