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

## Maximize Score after N Operations - Hard Level Problem

## Table of contents

### No headings in the article.

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:

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.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.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.Inside the nested loops, we check if the numbers represented by

`i`

and`j`

are selected in the current`mask`

(using bitwise AND).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).We update

`maxVal`

to store the maximum score obtained among all the pairs.Once the loop ends, we store the calculated

`maxVal`

for the current state in the`lookup`

table.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.

Initially, we call the

`maxScore`

function with the input vector`nums`

.In the

`maxScore`

function, we calculate the size of the input vector`m`

, which is 3 in this case.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.Inside the

`dp`

function, we check if the`mask`

is zero. Since it's not, we continue to the next step.We calculate a unique

`key`

based on the current step`a`

and the`mask`

. In this case,`key = 1 + 111 * 10 = 1121`

.We check if the calculated

`key`

exists in the`lookup`

table. Since it doesn't, we move to the next step.We initialize

`maxVal`

to 0. This variable will store the maximum score.We enter the nested loops to iterate over all possible pairs of indices

`(i, j)`

in the`nums`

vector.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.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`

.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`

.We continue the nested loop and repeat steps 9-11 for other valid pairs of indices

`(i, j)`

.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.

We store the calculated

`maxVal`

(5) for the current state (key = 1121) in the`lookup`

table.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.