Problem
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.
Examples
Solution
Method 1 – Dynamic Programming
Intuition
The key idea is to use dynamic programming to find the optimal sequence of key presses. At each step, we decide whether to press ‘A’ or to perform a sequence of ‘Ctrl-A’, ‘Ctrl-C’, and multiple ‘Ctrl-V’s to maximize the number of ‘A’s. The optimal solution at each step depends on the best result from previous steps.
Approach
- Create a DP array
dp
wheredp[i]
represents the maximum number of ‘A’s that can be produced withi
key presses. - For each
i
from 1 ton
:
- Set
dp[i] = dp[i-1] + 1
(pressing ‘A’). - For each possible earlier position
j
(wherej
ranges from 2 toi-1
):- Perform ‘Ctrl-A’ and ‘Ctrl-C’ at step
j-2
, then paste (i-j+1
) times. - Update
dp[i] = max(dp[i], dp[j-2] * (i-j+1))
.
- Perform ‘Ctrl-A’ and ‘Ctrl-C’ at step
- Return
dp[n]
as the answer.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n^2)
— For eachi
, we may check up toi
previous positions. - 🧺 Space complexity:
O(n)
— For the DP array.