Part 2 – Dynamic Programming – Solving problems with multiple state variables

Introduction:

For most DP problems, it is advisable to deduce the followings terms:

1. state: aka the subproblems which the answer to the problem could be derived from. Each subproblem is a state.
2. state variables: the inputs that define the state. They are also the inputs the goes in to recursive functions , if top-down approach is used, or the DP array's elements, if bottom up approach is used.
3. recurrence relation: indicates the transition between the states. If topdown approach is used, recursive functions and how those recursive are called should be defined. If bottom up approach is used, DP equation which defines how DP array is calculated is used. The common equation would be DP[currentStateVariable] = a * DP[nextStateVariables] + b.
4. base case.

DP problems may have several state variables. First is usually the index of operations, and some other are added based on problems' requirements.

The following problem illustrates the above systematic approaches to solve DP problems with multiple state variables.

Sample problem Maximum Scores from Performing Multiple 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] corresponds 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

Solution 1: Brute Force

We use recursive functions for recursive approach. Brute force solution is top-down code, but without memoization. Recursive calls generate a decision tree. Each branch has 2 child branches where:

• the index of operation i increase by 1
• the index of the leftmost element increases by 1
• the index of the rightmost element decreases by 1
• the parent node is the max value of 2 branches.

Code

class Solution {
    private:
    int nextOperation(vector<int> &nums, vector<int> &multipliers, int i, int left, int right){
        // base condition:
        if(i==multipliers.size())
            return 0;
        // recurrence relation:
        int scoreLeft= multipliers[i]*nums[left] + nextOperation(nums, multipliers, i+1, left+1, right);
        int scoreRight= multipliers[i]*nums[right] + nextOperation(nums, multipliers, i+1, left, right-1);

        return max(scoreLeft, scoreRight);
    }
    public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int m = multipliers.size();
        return nextOperation(nums, multipliers, 0, 0, nums.size()-1);
    }
};

Solution 2: Top-down with memoization

Approach

We approach any DP problems by figuring out state variable, state, base condition, relation recurrence.

1. state variable: at each state, when a new operation is carried out, we have 3 state variables:

   • i: the index of operations. zero-indexed
   • left: the index of the leftmost number remaining in nums. Conveniently, Left is also the number of left elements that have been picked.
   • right: the index of the rightmost number remaining in nums.
   • if i and left are given, then the total number of right elements that have been picked is i-left.
   • Therefore, right = nums.size() - 1 - the total number of right elements that have been picked or right= nums.size() - 1 -( i - left)
   • Therefore, 2 state variables are needed: i and left.

2. state: for top down approach, we use recursive call to generate the result from "decision tree". For example:

   • each branch has 2 child branches where state variable changes as: i++ and left++, right--
   • a 2D array size m x m is used to stored cache and thus optimized running time.

3. relation recurrence:

   • for any state, we get currentScore by multipliers[i]* nums[position] where:
   • position = left if we pick a number from the left, the current position = the number of elements have been picked from the left, including current element
   • position = right if we pick a number from the right
   • after that, we can move to the next state, by either choosing another element from the left or from the right. Thus the next state variable is i+1 and either left+1 or right-1.
   • if we pick a number from the left, make recursive call to: nextScore = nextOperation(nums, multi, i+1, left+1, right)
   • if we pick a number from the right: nextScore = nextOperation(nums, multi, i+1, left, right-1)

4. Base case:

   • it is intuitive to see that the recursive call should stop if the number of operation i reaches the size of the multiplier array.
   • when it happens, it should return 0 as there is no more element from the nums array.

Code

The credit for the followind code goes to Leetcode user: pratiksaha198

class Solution {
    private:
    vector<vector<int>> cache;
    int nextOperation(vector<int> &nums, vector<int> &multipliers, int i, int left, int right){
        // base condition
        if(i==multipliers.size())
            return 0;
        // memoization
        if(cache[left][i]!=-1)
            return cache[left][i];
        // recurrence relation
        int scoreRight = multipliers[i]*nums[left] + nextOperation(nums, multipliers, i+1, left+1, right);
        int scoreLeft = multipliers[i]*nums[right] + nextOperation(nums, multipliers, i+1, left, right-1);
        cache[left][i] = max(scoreLeft, scoreRight);
        return cache[left][i];
    }
    public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int m = multipliers.size();
        cache.resize(m, vector<int>(m,-1));
        return nextOperation(nums, multipliers, 0, 0, nums.size()-1);
    }
};

Complexity Analysis

• Time Complexity: O(m^2). We have 2 recursive calls, each of which runs m operations, thus O(M^2)
• Space Complexity: O(m^2). We have 2D cache array with size m x m, thus O (M^2)

Solution 2: Bottom-Up

Approach

We approach any DP problems by figuring out state variable, state, base condition, relation recurrence.

1. state variable: same as in topdow solution, we have 3 variables, i, left, right. However, we want to simplify the problem by using only 2 variables.
   • i is the number of operations have been done at any state. left is the number of left item have been picked.
   • if i and left are given, then the total number of right elements that have been picked is i-left.
   • Therefore, 2 state variables are needed: i and left.
2. state : for bottom up approach, we use 2D array structure DP[i][left] to store the score gained in any state.
   • the total number of operation is the size of multiplier array.
   • the max number of elements have been picked from the left is also the max number of operation.
   • Thus the size of DP array is n x n
   • for any state, we get currentScore by multipliers[i]* nums[position] where:
     • position = left if we pick a number from the left, the current position = the number of elements have been picked from the left, including current element
     • position = index of right number = nums.size() - 1 -( i - left) if we pick a number from the right
   • after that, we can move to the next state, by either choosing another element from the left or from the right. However, if we increment i keeping left constant, it would be ultimately equivalent to decrementing right, thus right-1 also means left unchanged.
   • if we pick a number from the left: nextScore = DP[i+1][left+1]
   • if we pick a number from the right: nextScore = DP[i+1][left]
3. relation recurrence: we define the relation by running a double for loop and calculate the state value. Since DP[][] is a 2D array, we need to analyze how to fill up data on the 2D array
   • Outer for loop: op goes from multiplier.size() to zero
   • Inner for loop: left goes from 0 to op. (left <=op)
4. Base case:

Code

Implementation with 2D array

Source: Leetcode editorial solution.

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        // For Right Pointer
        int n = int(nums.size());
        // Number of Operations
        int m = int(multipliers.size());
        vector dp(m + 1, vector<int>(m + 1, 0));
        
        for (int op = m - 1; op >= 0; op--) {
            for (int left = op; left >= 0; left--) {
                dp[op][left] = max(multipliers[op] * nums[left] + dp[op + 1][left + 1],
                                   multipliers[op] * nums[n - 1 - (op - left)] + dp[op + 1][left]);
            }
        }
        
        return dp[0][0];
    }
};

Implementation with 1D array

Note that we can move to the next state, by either choosing another element from the left or from the right. However, if we increment i keeping left constant, it would be ultimately equivalent to decrementing right, thus right-1 also means left unchanged.

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        // For Right Pointer
        int n = int(nums.size());
        // Number of Operations
        int m = int(multipliers.size());
        vector<int> dp(m + 1, 0);
        for (int op = m - 1; op >= 0; op--) {
            for (int left = 0; left <= op; left++) {
                dp[left] = max(multipliers[op] * nums[left] + dp[left + 1],
                               multipliers[op] * nums[n - 1 - (op - left)] + dp[left]);
            }
        }
        return dp[0];
    }
};

Complexity Analysis:

• Time complexity O(M^2) because of the double for loop where limit is the size of the multiplier array, or number of operations
• Space complexity O(M^2) because of the size of DP array m x m