4 Keys Keyboard — LeetCode 651 Python Solution

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

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