Leetcode Problem 1700-1799

1710. Maximum Units on a Truck 🌟

It is a greedy problem.
We just choose the box with the largest number of units per box.
We keep adding boxes and units*boxes until the total number of boxes on the truck is greater than truckSize.
finally, if we cannot take all boxes we take remaining required number of boxes and stop there.
Return the count of total units.
TC:O(N log N)
SC:O(1)

A greedy solution where for every index in multipliers vector you would choose the first or last one from the nums vector and then multiply it and keep on adding it to the sum.
This is not a correct solution as it fails when their are uneven number of +ve and -ve values in both vector.
Thus a recursive solution is required where all the possible values of choosing the leftmost num or rightmost num in nums vector are computed.Below is the implementation.
TC: O(2^N)

As we have a correct recursive code at hand, 90% of our Dynamic Programming solution is DONE.
We just have to memorize the recursive code into a 2-D array of (Size of nums) X (Size of multipliers) as its changing variables.
We initialize the 2-D array with -1, and keep on updating the smaller sub-solutions which is the maximum of choosing answer from leftmost or rightmost in nums vector.
If during a pass we find some sub-problem is already present, return the answer.
TC: O(2*m^2), where m<=10^3
SC: O(m^2)

We can convert the top-down approach to the bottom-up approach and hence reduce the recursive stack space.
TC: O(2*m^2), where m<=10^3
SC: O(m^2)