简介：4键键盘 dp medium
2 动态规划设计
2.11 不同定义产生不同解法
假设你有一个特殊的键盘包含下面的按键：
- A：在屏幕上打印一个 ‘A’。
- Ctrl-A：选中整个屏幕。
- Ctrl-C：复制选中区域到缓冲区。
- Ctrl-V：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。
现在，你可以 最多 按键 n 次（使用上述四种按键），返回屏幕上最多可以显示 ‘A’ 的个数 。
示例 1：
1
2
3
4
5
|
输入: n = 3
输出: 3
解释:
我们最多可以在屏幕上显示三个'A'通过如下顺序按键：
A, A, A
|
示例 2：
1
2
3
4
5
|
输入: n = 7
输出: 9
解释:
我们最多可以在屏幕上显示九个'A'通过如下顺序按键：
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
|
提示：
解法一
dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public int maxA(int n) {
//dp
//dp数组定义：dp[i]表示 最多 按键 i 次，屏幕上最多可以显示 'A' 的个数
int[] dp = new int[n+1];
//base case
dp[0] = 0;
//状态转移方程
for(int i = 1; i <= n; i++) {
dp[i] = dp[i-1] + 1;
for(int j = 2; j < i; j++) {
//从第j-2次开始执行 Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V ...
dp[i] = Math.max(dp[i], (i-j+1) * dp[j-2]);
}
}
//返回值
return dp[n];
}
}
|
