Special Keyboard

Imagine you have a special keyboard with the following keys:

• Key 1: Prints ‘A’ on screen
• Key 2: (Ctrl-A): Select 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.

Find maximum numbers of A’s that can be produced by pressing keys on the special keyboard N times.

• Time : O(2^n)
• Space : O(2^n)

class Solution{
public:
    long long int optimalKeys(int N){
        queue<array<long long int,3>> q;
        unordered_map<long long int, int> vis;
        q.push({1, 1, N - 1});
        long long int res = 0;
        while(!q.empty()) {
            array<long long int, 3> alli3 = q.front(); q.pop();
            long long int a = alli3[0], cp = alli3[1], n = alli3[2];
            if(n == 0) {
                res = max(res, a);
                continue;
            }
            if(!vis.count(a + cp) or vis[a + cp] < n - 1) {
                q.push({a + cp, cp, n - 1});
                vis[a + cp] = n - 1;
            }
            if(n >= 3 and (!vis.count(a + a) or vis[a + a] < n - 3)) {
                q.push({a + a, a, n - 3});
                vis[a + a] = n - 3;
            }
        }
        return res;
    }
};

• Time : O(n)
• Space : O(n)

As the number of A’s become large, the effect of pressing Ctrl-V more than 3 times starts to become insubstantial as compared to just pressing Ctrl-A, Ctrl-C and Ctrl-V again.

So We just calculate last 3 copy & paste operation

class Solution{
public:
    long long int optimalKeys(int N){
        if(N <= 6) return N;
        vector<long long int> dp(N, 0);
        for(int i = 0; i < 6; i++) dp[i] = i + 1;
        for(int i = 6; i < N; i++) {
            dp[i] = max({
                2 * dp[i-3],
                3 * dp[i-4],
                4 * dp[i-5]
            });
        }
        return dp.back();
    }
};