MediumNo. 0651LeetCode Premium
4 Keys Keyboard — LeetCode 651 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Math, Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Imagine you have a special keyboard with the following keys: A: Print one 'A' on the screen. Ctrl-A: Select the whole screen.
Example
- Input
- n = 3
- Output
- 3
- Explanation
- We can at most get 3 A's on screen by pressing the following key sequence:
Python solution
class Solution:
def maxA(self, n: int) -> int:
dp = list(range(n + 1))
for i in range(3, n + 1):
for j in range(2, i - 1):
dp[i] = max(dp[i], dp[j - 1] * (i - j))
return dp[-1]Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 651. 4 Keys Keyboard is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0650 | 2 Keys Keyboard | Medium |
| 0062 | Unique Paths | Medium |
| 0070 | Climbing Stairs | Easy |
| 0096 | Unique Binary Search Trees | Medium |
| 0233 | Number of Digit One | Hard |
| 0241 | Different Ways to Add Parentheses | Medium |
Frequently asked questions
- How hard is LeetCode 651. 4 Keys Keyboard?
LeetCode 651. 4 Keys Keyboard is rated Medium on LeetCode.
- What topics does LeetCode 651. 4 Keys Keyboard cover?
LeetCode 651. 4 Keys Keyboard is tagged Math and Dynamic Programming on LeetCode.
- Is LeetCode 651. 4 Keys Keyboard a premium problem?
Yes. LeetCode 651. 4 Keys Keyboard is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.