Daily Dose of DSA - Day 18

Question Link: https://practice.geeksforgeeks.org/problems/special-keyboard3018/1

Recursive DP :

The recursive calls in the given solution aim to find the maximum number of 'A's that can be produced by pressing keys on the special keyboard N times.

The approach can be summarized as follows:

1. For N <= 6 (the base cases), the maximum number of 'A's that can be produced is equal to N. So, if N is less than or equal to 6, directly return N.

2. For N > 6, the approach utilizes dynamic programming to calculate the optimal solution. It uses a DP array (dp) to store the results of subproblems.

3. Initialize the DP array with -1 for indices 0 to N, indicating that the values are not yet calculated.

4. Set the base cases of the DP array from 1 to 6 as their respective values (since pressing keys 1 to 6 individually will produce the same number of 'A's).

5. Use a helper function (computeOptimalKeys) to calculate the maximum number of 'A's for a given N, utilizing memoization to avoid redundant calculations.

6. In the computeOptimalKeys function, check if the result for the current N is already calculated in the DP array. If so, return the stored value.

7. If the result for the current N is not yet calculated, recursively call the computeOptimalKeys function for each possible key sequence (2, 3, 4, etc.). Multiply the result of the recursive call with a constant factor representing the number of times the key sequence is pressed, and take the maximum of these values.

8. Store the maximum result in the DP array for the current N.

9. Return the maximum result.

Code:

class Solution{

public:
 long long int optimalKeys(int N) {
        if (N <= 6) {
            return N; // Hit & Trial 
        }

        // Create a DP array to store the results of subproblems
        vector<long long> dp(N + 1, -1);

        // Base cases
        for(int i=1;i<=6;i++)
        {
            dp[i]=i;
        }

        return computeOptimalKeys(N, dp);
    }
     long long int computeOptimalKeys(int N, std::vector<long long>& dp) {
        if (dp[N] != -1) {
            return dp[N];
        }

        long long res = 0;

        // Recursive calls for each possible key sequence
        res = max(res, 2 * computeOptimalKeys(N - 3, dp)); // the key sequence: Key 2 (Ctrl-A), Key 3 (Ctrl-C), Key 4 (Ctrl-V), Key 4 (Ctrl-V)
        res = max(res, 3 * computeOptimalKeys(N - 4, dp)); // Key 2 (Ctrl-A), Key 3 (Ctrl-C), Key 4 (Ctrl-V), Key 4 (Ctrl-V)
        res = max(res, 4 * computeOptimalKeys(N - 5, dp)); //Key 2 (Ctrl-A), Key 3 (Ctrl-C), Key 4 (Ctrl-V), Key 4 (Ctrl-V), Key 4 (Ctrl-V)


        // Store the result in the DP array
        dp[N] = res;

        return res;
    }
};

The time complexity of the Recursive dynamic programming solution is O(N), where N is the given input number.

Iterative DP:

1. If the number of key presses, N, is less than or equal to 6, directly return N as the maximum number of 'A's that can be produced.

2. Initialize a dynamic programming array, dp, of size N+1 to store the maximum number of 'A's that can be produced for each number of key presses.

3. Handle the base cases where the maximum number of 'A's is equal to the number of key presses (from 1 to 6).

4. For each number of key presses from 7 to N, calculate the maximum number of 'A's by considering different key sequences (e.g., pressing Key 2, Key 3, Key 4).

5. Store the maximum number of 'A's in the dp array for each number of key presses.

6. Return dp[N] as the maximum number of 'A's that can be produced for N key presses.

7. Calculation of Maximum Number of A's -> each number of key presses from 7 to N, the maximum number of 'A's is calculated by taking the maximum among three possibilities:

   • Pressing Key 2 (Ctrl-A), Key 3 (Ctrl-C), Key 4 (Ctrl-V) once, and considering the maximum number of 'A's that can be produced from the remaining key presses.

   • Pressing Key 2 (Ctrl-A), Key 3 (Ctrl-C), Key 4 (Ctrl-V) twice, and considering the maximum number of 'A's that can be produced from the remaining key presses.

   • Pressing Key 2 (Ctrl-A), Key 3 (Ctrl-C), Key 4 (Ctrl-V) thrice, and considering the maximum number of 'A's that can be produced from the remaining key presses.

   • *2 -> Initial + one time CTRL+V

   • *3 -> Initial + two time CTRL+V

   • *4 -> Initial + three time CTRL+V

Code:

class Solution{
public:
 long long int optimalKeys(int N) {
       if (N <= 6) {
            return N;
        }

        vector<long long> dp(N + 1, 0);

        for (int i = 1; i <= 6; i++) {
            dp[i] = i;
        }

        for (int i = 7; i <= N; i++) {
            dp[i] = max({dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4});

        }

        return dp[N];
    }
};

The time complexity of this solution is O(N), as it involves a single loop iterating from 7 to N. The space complexity is also O(N) to store the dynamic programming array.