假设你有一个特殊的键盘包含下面的按键:
Key 1: (A):在屏幕上打印一个 'A'。
Key 2: (Ctrl-A):选中整个屏幕。
Key 3: (Ctrl-C):复制选中区域到缓冲区。
Key 4: (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
结果不会超过 32 位有符号整数范围。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/4-keys-keyboard 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int maxA(int N) {
vector<int> dp(N+1,0);
//dp[i] 表示,第 i 次按下键的最多A个数
for(int i = 1, j; i <= N; ++i)
{
dp[i] = max(dp[i], dp[i-1]+1);//按下A键
for(j = 0; j <= i-2; ++j)
//从前面可以的地方选一次进行ACV,后面一直V...
// -2 表示 AC的少了2次,后面可以一直粘(i-j-2)次 + 原来自己一次
dp[i] = max(dp[i], dp[j]*(i-j-1));
}
return dp[N];
}
};
0 ms 6.1 MB