LeetCode: 4 Keys Keyboard

4 Keys Keyboard

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #dynamicprogramming, maxprofitwithcost, #reachpoint

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 for N times (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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:

// https://code.dennyzhang.com/4-keys-keyboard
// Basic Ideas: dynamic programming
//
//  3 operations: double and print the buffer
//
//  When N is big, usually two strategies
//    Print buffer, or double-print buffer
//
//  1. insert one
//  2. paste previous: (use 2 steps to update the buffer)
//  dp(i) = max(i, dp(j)*(i-j-1))
//        1 <= j <= i-3
//        dp[j] * (i-2-j+1)
//
// Complexity: Time O(n^2), Space O(n)
func maxA(N int) int {
    dp := make([]int, N+1)
    for i, _ := range dp {
        dp[i] = i
    }
    for i:=1; i<len(dp); i++ {
        for j:=1; j<=i-3; j++ {
            // i-2-j+1
            if dp[j]*(i-j-1) > dp[i] {
                dp[i]= dp[j]*(i-j-1)
            }
        }
    }
    return dp[N]
}