动态规划
题目中提到的有四个按键,但实际上,我们可以压缩为2
个选择,因为对于最优解,Ctrl V一定在Ctrl A-Ctrl C两个按键后
- 【
dp
数组含义】:按键i次后屏幕显示dp[i]
个A
- 【状态】:剩余可按键数量
N
- 【选择】:①按A; ②按Ctrl V(需通过额外变量
j
来确定Ctrl C的位置,从而确定剪贴板中A
的个数dp[j - 2]
) - 【状态转移方程】:
dp[i] = max(dp[i - 1] 1, dp[j - 2] * (i - j 1));
class Solution {
public:
int maxA(int N) {
// dp数组含义:按键i次后屏幕显示dp[i]个A
vector<int> dp(N 1, 0);
// 压缩为2个选择 → [1]按A;[2]按Ctrl-V (包含前方必有的Ctrl-A Ctrl-C)
for (int i = 1; i <= N; i ) {
// [1]按A
dp[i] = dp[i - 1] 1;
// [2]按Ctrl-V (包含前方必有的Ctrl-A Ctrl-C)
for (int j = 2; j < i; j )
// dp[j - 2]表示剪贴板中A的个数,减去的2即为CA CC两个组合键
dp[i] = max(dp[i], dp[j - 2] * (i - j 1)); // 最多可按(i - j 1)个Ctrl-V
}
return dp[N];
}
};