题目描述
假设你有一个特殊的键盘包含下面的按键:
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
代码
动态规划 - Java
class Solution {
public int maxA(int n) {
// f[i]表示第i次按键,可以显示'A'的最大个数
int[] f = new int[n + 1];
for (int i = 1; i <= n; i++){// 枚举第i次按键
f[i] = f[i - 1] + 1;// case1 : 在屏幕上打印一个'A'
for (int j = 2; j + 2 <= i; j++){// case2 : Ctrl-A -> C -> V打印若干'A'
/**
第 j 步 执行Ctrl-A
第 j+1 步 执行Ctrl-C,复制了f[j-1]个'A'
剩下的 i - (j + 1) 步 执行Ctrl-V,屏幕上有f[j-1] + f[j-1] * (i - j - 1)个'A'
化简后为f[j-1] * (i - j)
*/
f[i] = Math.max(f[i], f[j - 1] * (i - j));
}
}
return f[n];
}
}