[LeetCode] 4 Keys Keyboard

651. 4 Keys Keyboard

Imagine you have a special keyboard with the following keys:

  • A: Print one ‘A’ on the screen.
  • Ctrl-A: Select the whole screen.
  • Ctrl-C: Copy selection to buffer.
  • Ctrl-V: Print buffer on screen appending it after what has already been printed.

Given an integer n, return the maximum number of ‘A’ you can print on the screen with at most n presses on the keys.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxA(int n) {
vector<int> dp(n + 3);
for(int i = 1; i <= n; i++) {
dp[i] = i;
for(int j = 1; j < i - 2; j++) {
dp[i] = max(dp[i], dp[j]*(i-j-1));
}
}
return dp[n];
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/04/03/PS/LeetCode/4-keys-keyboard/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.