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 vectornums
.
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 stepa
and themask
. This key is used to check if we have already computed and stored the result for this state in thelookup
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 thenums
vector.Inside the nested loops, we check if the numbers represented by
i
andj
are selected in the currentmask
(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) ofnums[i]
andnums[j]
. We add this score to the result obtained from the next recursive call todp
with the updatedmask
(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 thelookup
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 vectornums
.In the
maxScore
function, we calculate the size of the input vectorm
, which is 3 in this case.We then call the
dp
function with the initial parametersa = 1
,nums = [1, 2, 3]
,mask = (1 << 3) - 1
, andm = 3
. Here,mask
is initially set to111
in binary, representing that all three numbers are available for selection.Inside the
dp
function, we check if themask
is zero. Since it's not, we continue to the next step.We calculate a unique
key
based on the current stepa
and themask
. In this case,key = 1 + 111 * 10 = 1121
.We check if the calculated
key
exists in thelookup
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 thenums
vector.In the first iteration,
i = 0
andj = 1
. We check if both numbers are selected in the currentmask
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) ofnums[i]
andnums[j]
. So, the score is1 * gcd(1, 2) = 1
.We add this score to the result obtained from the next recursive call to
dp
with the updatedmask
. In the updatedmask
, we remove the selected numbers by performing bitwise XOR operations. So, the updatedmask
becomesmask ^ (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 thelookup
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.