leetcode 651. 4键键盘

651. 4键键盘

中等 102 company 微软 Microsoft company 谷歌 Google company 亚马逊

假设你有一个特殊的键盘包含下面的按键：

• A：在屏幕上打印一个 ‘A’。
• Ctrl-A：选中整个屏幕。
• Ctrl-C：复制选中区域到缓冲区。
• Ctrl-V：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

现在，你可以 最多 按键 n 次（使用上述四种按键），返回屏幕上最多可以显示 ‘A’ 的个数 。

示例 1:

输入: n = 3
输出: 3
解释: 我们最多可以在屏幕上显示三个’A’通过如下顺序按键： A, A, A

示例 2:

输入: n = 7
输出: 9
解释: 我们最多可以在屏幕上显示九个’A’通过如下顺序按键： A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

提示:

1 <= n <= 50

解析：

• 一个位置上的数可以由前边数复制过来，也可以时在前一个数的最大值上+1
• 并且还可以连续复制，因此枚举赋值其实点
• 在连续复制期间，执行操作一这种操作肯定不如接着复制，因此，考虑连续复制是不用想那么复杂；

代码：

class Solution {
public:// f[i] 表示 i 个元素的最大值// f[i]  = max(f[i-j]*可复制长度,f[i-1]+1)int maxA(int n) {int f[51];memset(f, 0, sizeof(f));f[1]=1,f[2]=2,f[3]=3;for(int i=4;i<=n;i++){int res = f[i-1]+1;// 枚举连续复制的起点，前两个操作为a,c中间的操作都是复制for(int j=i-3;j>=0;j--){res = max(f[j]*(i-j-1),res);}f[i] = res;}return f[n];}
};