651. 4 Keys Keyboard
Imagine you have a special keyboard with 4 keys:
- A: Prints 'A' on screen
- Ctrl-A: Select all
- Ctrl-C: Copy selection
- Ctrl-V: Paste
Given n keystrokes, maximize the number of 'A's displayed on screen.
Examples
Input: 3
Output: 3
Input: 7
Output: 9
Hints
Use dynamic programming where dp[i] represents the maximum As with i keystrokes.
The key insight is that copy-paste operations can be optimized by considering different split points.
For each i, try split at j: dp[i] = max(dp[j] * (i - j - 1)) for j < i
Related Problems
651. 4 Keys Keyboard
Imagine you have a special keyboard with 4 keys: