4 Keys Keyboard

Imagine you have a special keyboard with the following keys:

Key 1: (A): Print one 'A' on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard forNtimes (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

Example 1:

Input:
 N = 3

Output:
 3

Explanation:

We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input:
 N = 7

Output:
 9

Explanation:

We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

1. 1

   <

   = N

   <

   = 50

2. Answers will be in the range of 32-bit signed integer.

分析

I可以直接print来，不copy, dp[i] = i

j之前print, j之后都copy, j的 range = [1,i-3] . dp[i] = dp[j]*(i-j-1)

从j到i状态转换，去掉2次选择和复制操作，剩下的都是粘贴C，i的个数是j的C倍。

class Solution:
    def maxA(self, N: int) -> int:
        dp=[0]*(N+1)
        for i in range(1,N+1):                        
            dp[i] = i
            for j in range(1,i-3):
                dp[i] = max(dp[i], dp[j]*(i-j-1))

        return dp[N]