Playing around with dynamic programming

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

Let’s see how to use this technique to our advantage.

Maximum Score from Performing Multiplication Operations

You are given two 0-indexed integer arrays nums and multipliers of size n and m respectively, where n >= m.

You begin with a score of 0. You want to perform exactly m operations. On the ith operation (0-indexed), you will:

• Choose one integer x from either the start or the end of the array nums.
• Add multipliers[i] * x to your score. Note that multipliers[0] correspond to the first operation, multipliers[1] to the second operation, and so on.
• Remove x from nums.

Return the maximum score after performing m operations.

Example 1

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Example 2

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

Constraints

• n == nums.length
• m == multipliers.length
• 1 <= m <= 300
• m <= n <= 105
• -1000 <= nums[i], multipliers[i] <= 1000

Brute Force Solution:

This exercise asks us to maximize the points we can get after m operations. A solution for this would be to simulate all possible scenarios: visit all the possible m operations we can make, compare the points obtained, and keep the highest one.

This algorithm would look something like this:

Solve called with m(number of operations):
  if m is equal 0: return 0 
  
  index <- length of multipliers - m  

  value <- get and delete the first element of nums
  option1 <- solve called with (m-1) operations + multipliers at index * value
  
  restore nums with value at its front.

  value <- get and delete the last element of nums
  option2 <- solve called with (m-1) + to multipliers at index * value
  
  restore nums with value at its end.  

  return the maximum between option1 and option2


Our Solution should be call Solve with m

Let’s show that solve called with m operations, with an array nums and multipliers, returns the maximum score after performing m operations. For this purpose, we will use mathematical induction:

Preposition:

For any n in the set of natural numbers solve(n) returns the maximum score after performing n operations with any nums and multipliers.

Base Case:

solve called with n=0 returns 0, which is correct since the highest possible score of performing 0 operations in any nums and multipliers is 0.

Hypothesis:

If n=k, being k a natural number, solve(n) returns the maximum score after performing k operations with any nums and multipliers.

Tesis:

If n=k+1, and we call solve(n) our algorithm will consider two options:

It will choose one integer x from the start of the array nums. And it will calculate x*multipliers[i] where i is the ith operation + maximum score possible of k operation with nums without the first element and multiplier without first element(solve(k) because our hypothesis).

It will choose one integer x from the end of the array nums. And it will calculate x*multipliers[i] where i is the ith operation + maximum score possible of k operation with nums without the last element and multiplier without first element(solve(k) because our hypothesis).

Once the two have been calculated, the maximum will be returned.

i.e. we return the maximum of performing one of the two possible operations plus the maximum of solving the problem in k.

Suppose it is not correct, we perform one of the two possible operations, but the solution is not that plus solve with k operations. So there must be a way to get a greater score by performing k operations with what is subtracted from the array num and the array multiplier. This contradicts our hypothesis, it is absurd. Then solve(k+1) returns the highest score of performing k+1 operations.

In this way our preposition is proved.

We have already demonstrated the correctness of our algorithm. Let us now look at the time complexity. In each call we make to solve, we take two operations and call back in m-1, i.e., we perform 2^m operations, and our algorithm is O(2^m). Since m can become 300, our computer suffers a bit performing those 2³⁰⁰ operations. This algorithm is not as efficient as it should be; will this be our end?

Here’s the code in Java:

class Solution {
    int n;
    int[] nums, multipliers;

    private int solve(int m, int front){
        if(m==0) return 0;

        int index = multipliers.length-m;
        int last = n-1 - (index-front);

        int res = solve(m-1, front+1) + multipliers[index]*nums[front];
        res = Math.max(res, solve(m-1, front) + multipliers[index]*nums[last]);

        return res;
    }

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

        this.nums=nums;
        this.multipliers=multipliers;

        return solve(m,0);
    }
}

DP to the rescue!

Fortunately, dynamic programming is here to help us complete our tasks.

Our algorithm depends on a subproblem, we compute solve at m-1 for m. That’s all we need to implement dynamic programming.

We are going to create a two-dimensional array of mxm that we are going to name dp. dp[i][j] will represent the maximum points obtained from performing i operations and taking j elements from the beginning of nums, with a subarray of nums from j to n-1-(m-i-j) and a subarray of multipliers from m-i to its end. It may seem confusing, but those subarrays result from what remains after performing m-ioperations.

dp is a matrix of length mxm

Solve called with m(number of operations) and j(number of elements taken from the beginnig of nums):
  if m is equal 0: return 0 
  if dp[m][j] is already calculated: return dp[m][j]
  
  index <- length of multipliers - m  

  value <- get and delete the first element of nums
  option1 <- solve called with (m-1) operations + multipliers at index * value
  
  restore nums with value at its front.

  value <- get and delete the last element of nums
  option2 <- solve called with (m-1) + to multipliers at index * value
  
  restore nums with value at its last. 
 
  dp[m][j] <- the maximum between option1 and option2

  return dp[m][j]

Our Solution should be call Solve with m and 0

Our modified algorithm follows the same logic as our previous approach, only now we avoid calculating solutions to subproblems we have already calculated. With this, we only perform m² operations, which is how long it takes to fill our matrix dp. Once dp[i][j] is computed, calling solve(i,j) is O(1). So our algorithm has improved, and now its time and space complexity is O(m²).

In the worst case, our computer is going to perform 9*10⁴ operations. If our computer could talk, I am sure it would thank us.

Code:

class Solution {
    int n;
    int[] nums, multipliers;
    int[][] dp;
    boolean[][] mask;

    private int solve(int m, int front){
        if(m==0) return 0;
        if(mask[m][front]) return dp[m][front];

        int index = multipliers.length - m;
        int last = n-1 - (index-front);

        int res = solve(m-1, front+1) + multipliers[index]*nums[front];
        res = Math.max(res, solve(m-1, front) + multipliers[index]*nums[last]);
        mask[m][front] = true;

        return dp[m][front]=res;
    }

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

        dp = new int[m+1][m];
        mask = new boolean[m+1][m];
        this.nums=nums;
        this.multipliers=multipliers;

        return solve(m,0);
    }
}

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n = nums.size();
        int m = multipliers.size();
        
        vector<vector<int>> dp(m+1, vector<int>(m));
        
        function<int(int,int)> solve = [&](int op, int front)-> int {
            if(!op) return 0;
            if(dp[op][front]) return dp[op][front];
            
            int index = m-op;
            int last = n  - (index - front) -1;
            int res = solve(op-1, front+1) + multipliers[index]*nums[front];
            
            return dp[op][front] = max(res, 
                                (solve(op-1, front) + multipliers[index]*nums[last]) );
            
        };
        
        return solve(m,0);
    }
};

Summary:

The article above shows how dynamic programming allowed us to achieve greater efficiency from an extremely inefficient algorithm. This technique can be employed in many scenarios; the only condition is to modulate the problem to a solution that uses the solution of a subproblem.

Also:

If you want to try a solution to this problem, you can do it at this link.

Likewise, if you want to learn more about dynamic programming, I think these videos will be very helpful:

Finally, this link will help you to become a master of dynamic programming.