LeetCode 651 4 Keys Keyboard

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

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/