Leetcode 1770 Maximum Score from Performing Multiplication Operations | DP Coding Decoded SDE Sheet

Here is the solution to "Find Original Array From Doubled Array" leetcode question. Hope you have a great time going through it.

🔴 Connect with me here:
------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------
Master Data Structures and algorithms 🔽🔽🔽🔽

👉 Solution

🔥🔥🔥🔥👇👇👇 For discussion/feedback/humour/doubts/new openings

🔴 Checkout the series:

✨ Hashtags ✨
#CodingDecoded #ProductBased #SoftwareEngineering #FAANGM #FAANG #NSIT #NSUT #engineering #internship #college #Freshers #amazon #apple #coding

[souravdas]

Your explanation is always simple and sorted, thanks a lot.

[anshulsinha]

Thanks a lot, Sunchit Sir. Great approach and explanation as always !!

[chandnibhatia]

How do we understand that a question belongs to DP !

[tanson]

I am still not clear on how to use DP. I prefer using a map for the memo object as I don't have to worry about the size but I make the key with all changing values in the recursive call for example if I were to use your dp method my map key would be l+"-"+r+"-"+i. How do you decide what are the best values put in memo object?

Secondly I realized, nums[l]*muls[l]+maximumScore(nums, muls, i+1, l+1, r) != maximumScore(nums, muls, i+1, l+1, r, )+nums[nl]*muls[ml]. I mean if the dp call comes after the multiplication its memory utilization/runtime changes compared to the opposite order.

[tanson]

I see your second approach works without the complicated way of finding right ie nums[n-(i-l)-1], correct me if I am missing something.

public int maximumScore(int[] nums, int[] muls) {
n = nums.length;
m = muls.length;

this.memo = new Integer[m][m];
return dp(0, 0, nums, muls, n-1);
}
private int dp(int l, int i, int[] nums, int[] muls, int r) {
if (i == m) return 0; // Picked enough m elements
if (memo[l][i] != null) return memo[l][i];
int pickLeft = dp(l+1, i+1, nums, muls, r) + nums[l] * muls[i];
int pickRight = dp(l, i+1, nums, muls, r-1) + nums[r] * muls[i];
return memo[l][i] = Math.max(pickLeft, pickRight);
}