DSA - Maximize Score after N Operations - C++,Dynamic Programming

Hey, so today we are going to solve Leetcode - Maximize Score after N Operations

Problem Link- https://leetcode.com/problems/maximize-score-after-n-operations/description/

class Solution {
public:
   unordered_map<int, int> lookup;

   int dp(vector<int>& nums, int a, int mask, int size) {
   if(mask == 0) return 0; 
   int key = a + 10*mask; 

   if(lookup.find(key) == lookup.end()) {
   for(int i =0; i<m; i++){
      int maxVal = 0; 
      if(mask&(1<<i)){
      for(int j = i+1; j < m; j++) {
        if(mask&(1<<j)){
        maxVal = max(maxVal, a* __gcd(nums[i], nums[j]) + dp(nums, a+1, mask^(1<<i)^(1<<j), size)); 
        } 
        }
      }
     lookup[key] = maxVal;
   }
   }

   return lookup[key]; 
   } 

   int maxScore(vector<int>& nums) {
   int m = nums.size(); 

   dp(nums, 1, (1<<m)-1, m); 
   }
}

This code provides a solution to the "Maximize Score After N Operations" problem. It uses dynamic programming and recursion to find the maximum possible score.

The dp function is a recursive helper function that calculates the maximum score for a given state. It takes four parameters:

• a: Represents the current step in the recursion.

• nums: The input vector of integers.

• mask: A bitmask that represents the selected numbers at the current step.

• m: The size of the input vector nums.

The lookup variable is an unordered map that serves as a memoization table. It stores previously calculated results to avoid redundant computations and improve efficiency.

Now, let's go through the dp function in detail:

1. If the mask becomes zero, it means all the numbers have been used, and we have reached the end of the recursion. In this case, we return 0, as there are no more operations to be performed.

2. We calculate a unique key based on the current step a and the mask. This key is used to check if we have already computed and stored the result for this state in the lookup table.

3. If the result for the current state is not present in the lookup table, we calculate it by iterating over all possible pairs of indices (i, j) in the nums vector.

4. Inside the nested loops, we check if the numbers represented by i and j are selected in the current mask (using bitwise AND).

5. If both numbers are selected, we calculate the score for the current step a by multiplying it with the greatest common divisor (gcd) of nums[i] and nums[j]. We add this score to the result obtained from the next recursive call to dp with the updated mask (after removing the selected numbers).

6. We update maxVal to store the maximum score obtained among all the pairs.

7. Once the loop ends, we store the calculated maxVal for the current state in the lookup table.

8. Finally, we return the maximum score for the current state from the lookup table.

Now let's understand this question with an example

Suppose we have the input vector nums = [1, 2, 3]. We want to find the maximum score after performing a certain number of operations. Let's go through the code step by step with this example.

1. Initially, we call the maxScore function with the input vector nums.

2. In the maxScore function, we calculate the size of the input vector m, which is 3 in this case.

3. We then call the dp function with the initial parameters a = 1, nums = [1, 2, 3], mask = (1 << 3) - 1, and m = 3. Here, mask is initially set to 111 in binary, representing that all three numbers are available for selection.

4. Inside the dp function, we check if the mask is zero. Since it's not, we continue to the next step.

5. We calculate a unique key based on the current step a and the mask. In this case, key = 1 + 111 * 10 = 1121.

6. We check if the calculated key exists in the lookup table. Since it doesn't, we move to the next step.

7. We initialize maxVal to 0. This variable will store the maximum score.

8. We enter the nested loops to iterate over all possible pairs of indices (i, j) in the nums vector.

9. In the first iteration, i = 0 and j = 1. We check if both numbers are selected in the current mask by performing bitwise AND operations. In this case, they are both selected.

10. We calculate the score for the current step a by multiplying it with the greatest common divisor (gcd) of nums[i] and nums[j]. So, the score is 1 * gcd(1, 2) = 1.

11. We add this score to the result obtained from the next recursive call to dp with the updated mask. In the updated mask, we remove the selected numbers by performing bitwise XOR operations. So, the updated mask becomes mask ^ (1 << i) ^ (1 << j) = 111 ^ (1 << 0) ^ (1 << 1) = 101.

12. We continue the nested loop and repeat steps 9-11 for other valid pairs of indices (i, j).

13. Once the nested loop ends, we have calculated the maximum score among all the pairs. In this example, let's say the maximum score obtained is 5.

14. We store the calculated maxVal (5) for the current state (key = 1121) in the lookup table.

15. Finally, we return the maximum score (5) from the lookup table.

This process continues for different steps and masks until the recursive calls reach the base case where mask becomes zero. The lookup table helps avoid redundant computations by storing previously calculated results.

By using dynamic programming and memoization, the code efficiently explores different combinations and calculates the maximum score for the given input vector.