Dynamic Programming

1. Introduction to Dynamic Programming
2. Applications
3. Steps to solve a DP Problem
4. Approaches to Dynamic Programming
5. Example: Fibonacci Sequence
6. Example: Knapsack Problem
7. Leetcode Problems
8. References

1 Introduction to Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure, which are described below:

Overlapping subproblems

A problem has overlapping subproblems if it can be broken down into subproblems which are reused several times. For example, in the Fibonacci sequence, to calculate Fib(5), one needs Fib(4) and Fib(3), but Fib(4) itself requires Fib(3) and Fib(2). Here, Fib(3) is calculated multiple times, which is an overlapping subproblem.
Optimal substructure

A problem has an optimal substructure if an optimal solution to the problem contains within it optimal solutions to the subproblems. For instance, in the shortest path problem, if the shortest path from point A to point C goes through point B, then the shortest path from A to B is also part of the shortest path from A to C.

2 Applications

Dynamic programming has a wide range of applications, including:

Optimization: knapsack problem, shortest path problem, maximum subarray problem
Computer science: longest common subsequence, edit distance, string matching
Operations research: inventory management, scheduling, resource allocation

3 Steps to solve a DP Problem

Characterize the structure of an optimal solution.
- Identify how a solution to the problem can be composed of solutions to subproblems.
Define the value of an optimal solution recursively in terms of smaller subproblems.
- Write down a recurrence relation for the value of an optimal solution.
Compute the value of an optimal solution (typically in a bottom-up fashion).
- Use the recurrence relation to compute the value of an optimal solution, starting with the smallest subproblems and working upwards.
Construct an optimal solution from computed information.
- (Optional) If you need to not only find the value of the optimal solution but also construct the solution itself, backtrack through the computed information to construct the solution.

4 Approaches to Dynamic Programming

There are two main approaches to implement dynamic programming:

Top-Down (Memoization)
- This approach uses recursion to solve the subproblems.
- A memoization table is maintained to store the results of solved subproblems.
- When a subproblem is encountered, the table is checked to see if the result is already computed. If it is, the result is used directly. If not, the subproblem is solved and the result is stored in the table.
Bottom-Up (Tabulation)
- This approach involves solving subproblems first, thus building up the solution to the larger problems.
- It typically uses iteration and fills up a DP table in a way that depends on the values of smaller subproblems.
- This method ensures that the subproblems are solved before being called upon by a larger subproblem.

5 Example: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n - 1) + Fib(n - 2) for n > 1

When you compute the Fibonacci sequence using a simple recursive method, you will find that the same values are calculated multiple times. For example, to calculate Fib(5), you need Fib(4) and Fib(3). However, to calculate Fib(4), you need Fib(3) and Fib(2). Here, Fib(3) is calculated twice, and as you go higher in the sequence, the number of redundant calculations grows exponentially. This redundancy is known as overlapping subproblems.

The Fibonacci sequence exhibits optimal substructure because the solution to the problem (finding Fib(n)) can be constructed from the solutions to its subproblems (Fib(n-1) and Fib(n-2)). The optimal solution to finding Fib(n) inherently contains within it the optimal solutions to finding Fib(n-1) and Fib(n-2).

Memoization involves writing the function in a recursive manner but with a twist: we store the results of each Fibonacci computation in a data structure (usually an array or a dictionary) so that if the same computation is needed again, it can be retrieved from the storage instead of being computed again.

The following is a more detailed C++ code example using memoization.

int fibonacci_mem(int n, vector<int>& mem) {
    if (n < 2)
        return n;
    if (mem[n] != -1)
        return mem[n];
    mem[n] = fibonacci_mem(n - 1, mem) + fibonacci_mem(n - 2, mem);
    return mem[n];
}

int main() {
    int n = 20; // for example
    vector<int> mem(n + 1, -1);
    cout << "Fib(" << n << ") = " << fibonacci_mem(n, mem) << "\n";
}

Tabulation is the opposite of memoization. Instead of starting from the top and working down, we start from the bottom and fill up a table (usually an array) with the results of the subproblems.

The following is a C++ code example using tabulation.

int fibonacci_tab(int n) {
    if (n < 2)
        return n;
    vector<int> tab(n + 1, -1);
    tab[0] = 0;
    tab[1] = 1;
    for (int i = 2; i <= n; i++)
        tab[i] = tab[i - 1] + tab[i - 2];
    return tab[n];
}

By using dynamic programming, we can reduce the time complexity of calculating the nth Fibonacci number from exponential (as in plain recursion) to linear (using memoization or tabulation). This is a significant improvement, especially for large values of n. Dynamic programming efficiently solves problems with overlapping subproblems and optimal substructure by reusing previously computed results and building the solution from these results.

6 Example: Knapsack Problem

Given a set of n items numbered from 1 up to n, each with a weight w_i and a value v_i, and a bag with capacity W. The task is to put the items into the bag, such that the sum of the values is the maximum possible, and the sum of the weights is less than or equal to the bag's capacity.

The naive solution is to consider all subets of the items, and calculate the weights and values of all the subsets. From the subsets whose total weight is less than W, pick the subset with maximum total value.

There are only 2 choices for each item, either to include in the bag or ignore the item. For the n items, there are 2ⁿ choices in total. When we go through all combinations, the running time will be O(2ⁿ).

Can we do better? Yes, with an algorithm based on dynamic programming.

We notice that same subproblems are solved multiple times when using the naive recursive approach. For example, when deciding whether to include or exclude an item, you might end up calculating the optimal solution for the same remaining weight multiple times.

Secondly, the problem can be broken down into smaller, simpler subproblems, which can be used to construct the solution to the larger problem. If an item is included in the optimal subset, then the remaining items must constitute an optimal subset for the remaining weight limit.

Observing the 2 properties in the knapsack problem, we can do better with dynamic programming.

Let KP(1, n, W) denote the Knapsack problem, choosing items from [1…n] under capacity constraint W.

If (x₁, x2, .., x_n) is an optimal solution for the problem KP(1, n, W), for the two cases:

If x_n = 0, meaning the n_th item is not chosen, then (x₁, x₂, .., x_{n - 1}) must be an optimal solution for the problem KP(1, n - 1, W).
If x_n = 1, meaning the n_th item is chosen, then (x₁, x₂, .., x_{n - 1}) must be an optimal solution for the problem KP(1, n - 1, W - w_n).

Let S[n, W] be the value of the optimal solution for KP(1, n, W).

S[n, W]
= max(values for case 1, values for case 2)
= max(S[n - 1, W], S[n - 1, W - w_n] + v_n)

We can use a 2D table to memorize S[*, *]; to compute S[n, W], we need the values from the previous row: S[n-1, *]. Therefore, the table S can be built row by row from the first row.

Thus, the solution, the best total value, will be

if i == 0 or W = = 0:
- S[i, W] = 0
- Note. When i == 0, no object is chosen
- Note. When W == 0, no capacity is available
if w_i > W:
- S[i, W] = S[i - 1, W]
- Note. The weight (w_i) of the current (i) object exceeds the capacity, so we cannot pick it. The value equals to the one in the previous row with the same weight.
if i > 0 and W > w_i:
- S[i, W] = max(S[i - 1, W], S[i - 1, W - w_i] + v_i)
- Note. The best value is the maximum value of the 2 cases:
  - S[i - 1, W], when skipping item i, the value equals to the one in the previous row with the same weight.
  - S[i - 1, W - w_i] + v_i, when picking item i, the value equals to the value of item i, plus the value in the previous row with the weight W minus the weight of item i.

The following is a C++ function that implements the knapsack problem using dynamic programming with momorization recursive approach.

int knapsack(vector<int>& w, vector<int>& v, int i, int W, vector<vector<int>>& S) {
    if (i < 0)
        return -1;
    if (S[i][W] != -1)
        return S[i][W];

    if (i == 0 || W == 0)
        return 0;
    else if (w[i] > W) {
        S[i][W] = knapsack(w, v, i - 1, W, S);
        return S[i][W];
    }
    else {
        S[i][W] = max(knapsack(w, v, i - 1, W, S),
                      knapsack(w, v, i - 1, W - w[i], S) + v[i]);
        return S[i][W];
    }
}

The dynamic programming solution to the Knapsack problem is efficient and avoids the redundancy of recalculating the optimal solution for the same subproblems, which is a significant improvement over the naive recursive approach. The time complexity of this dynamic programming solution is O(nW), where 'n' is the number of items and 'W' is the maximum weight capacity, making it a pseudo-polynomial time algorithm. This approach is particularly useful when the number of items and the weight capacity are not too large.

7 Leetcode Problems

Now, let us solve more problems using the dynamic programming techniques. Note that some problems may have solutions that do not involve dynamic programming. We are not covering those in this article.

To solve 70. Climbing Stairs, we can build a table containing the number of ways to reach each step from the bottom. Since for each step, we could only come from 1 or 2 steps previously, the number of ways to reach this step will be equal to the sum of the number of ways to reach the previous step and the step before that.

int climbStairs(int n) {
    if (n <= 2)
        return n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    return dp[n];
}

It can be further optimized by storing the results in two variables instead of a vector. This will improve the space complexity from O(n) to O(1). space complexity will improve from O(n) to O(1).

int climbStairs(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int curr = 0;
    for (int i = 3; i <= n; i++) {
        curr = pre2 + pre1;
        pre2 = pre1;
        pre1 = curr;
    }
    return curr;
}

746. Min Cost Climbing Stairs is another problem relating to climb stairs. It asks for the minimum costs to reach the top of the floor. We build the table containing the costs at each step. Since for each step, we could only come from 1 or 2 steps previously, the minimum cost to reach a certain step will be the miminum of the two: the minimum cost to reach the previous step plus the cost from the previous step to current step, or the minimum cost to reach the step before that plus the cost from that step to the current step.

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1);
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
    }
    return dp[n];
}

Similarily, the space can be further optimized as follows.

int minCostClimbingStairs(vector<int>& cost) {
    int pre2 = 0, pre1 = 0, curr = 0;
    for (int i = 2; i <= cost.size(); i++) {
        curr =  min(pre2 + cost[i - 2], pre1 + cost[i - 1]);
        pre2 = pre1;
        pre1 = curr;
    }
    return curr;
}

For the problem 198. House Robber, we can calculate when walking through the houses once. Since the two adjacent houses cannot be robbed, the maximum amount of money at a certain house is one of the two cases: the maximum money we got at the previous house (implying the current house is skipped), or the maximum money we got at the house before the previous one plus the money robbing the current house (implying that the previous house is skipped).

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1)
        return nums[1];

    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = nums[1];
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }

    return dp[n - 1];
}

Similarily, the space can be further optimized as follows.

int rob(vector<int>& nums) {
    int pre2 = 0, pre1 = 0, curr = 0;

    for (int i = 0; i < nums.size(); i++) {
        curr = max(pre2 + nums[i], pre1);
        pre2 = pre1;
        pre1 = curr;
    }

    return pre1;
}

In the problem 213. House Robber II, the houses are arranged in a circle. Building on the solution for the previous problem, we can reduce this problem to robbing houses within a specific range, where the starting house and the ending house are not adjacent. The answer will be the maximum between two cases: either robbing from the second house to the last house (skipping the first one), or robbing from the first house to the second-to-last house (skipping the last one). The overall time complexity remains O(n).

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1)
            return nums[1];
        return max(robber(nums, 1, n - 1),
                   robber(nums, 0, n - 2));
    }
private:
    int robber(vector<int>& nums, int lo, int hi) {
        int pre2 = 0, pre1 = 0, curr = 0;
        for (int i = lo; i <= hi; i++) {
            curr = max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = curr;
        }
        return pre1;
    }
};

For the problem 2369. Check if There is a Valid Partition for the Array, we can create a dp vector, where each element represents whether there is a valid partition for the sub-array from index 0 to i - 1 of the array nums. The first element (dp[0]) is true because no invalid subarray can be partitioned from an empty array. The third element (dp[2]) depends on whether the first number (index 0) and the second number (index 1) are the same. For each subsequent element in the dp vector, it can be valid if one of the following conditions is satisfied:

The subarray is valid from index 0 to i - 3 and the numbers at index i - 2 and i - 1 are equal.
The subarray is valid from index 0 to i - 4 and the numbers at index i - 3, i - 2, and i - 1 are equal.
The subarray is valid from index 0 to i - 4 and the numbers at index i - 3, i - 2, and i - 1 are increasing with a difference of 1.

The answer will be the value of the last element in the dp vector.

int validPartition(vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    dp[2] = nums[0] == nums[1];
    for (int i = 3; i <= n; i++) {
        if ((dp[i - 2] && nums[i - 2] == nums[i - 1]) ||
            (dp[i - 3] && nums[i - 3] == nums[i - 2] && nums[i - 2] == nums[i - 1]) ||
            (dp[i - 3] && nums[i - 2] - nums[i - 3] == 1 && nums[i - 1] - nums[i - 2] == 1))
        {
            dp[i] = true;
        }
    }
    return dp[n];
}

Since only the most recent three elements of validity need to be referenced, the space can be further optimized as follows.

int validPartition(vector<int>& nums) {
    vector<bool> dp = {true, false, nums[0] == nums[1]};
    for (int i = 3; i <= nums.size(); i++) {
        bool curr = (dp[1] && nums[i - 2] == nums[i - 1]) ||
                    (dp[0] && nums[i - 3] == nums[i - 2] && nums[i - 2] == nums[i - 1]) ||
                    (dp[0] && nums[i - 2] - nums[i - 3] == 1 && nums[i - 1] - nums[i - 2] == 1);
        dp[0] = dp[1];
        dp[1] = dp[2];
        dp[2] = curr;
    }
    return dp[2];
}

For the problem 300. Longest Increasing Subsequence, we create a dp vector the same size as the input numbers, with each element representing the LIS values starting at the corresponding index. We calculate the LIS by iterating through the input numbers from the last element to the first. For each element at index curr, we need to check the LIS elements with larger indices next. If the integer at curr is less than the integer at next, meaning the subsequence starting at curr concatenated with the subsequence starting at next is valid, we then update the length accordingly. The result will be the maximum element in the LIS vector, considering that the subsequence can start with the integer at any index. The time complexity is O(n²) and the space complexity is O(n).

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty())
            return 0;

        int n = nums.size();
        vector<int> dp(n, 1);

        for (int curr = n - 1; curr >= 0; curr--) {
            for (int next = curr + 1; next < n; next++) {
                if (nums[curr] < nums[next])
                    dp[curr] = max(dp[curr], 1 + dp[next]);
            }
        }

        return *max_element(dp.begin(), dp.end());
    }
};

For the problem 322. Coin Change, we create a dp vector with a length of amount + 1. The i_th element represents the minimum number of coins needed to make up the value i. We iterate through the elements and update when there is a combination with a fewer number of coins, considering all possible combinations. The number of coins in a combination is calculated as 1 plus the value of the previous element at index i minus the value of a coin. The time complexity is O(n * m) and the space complexity is O(m), where n is the number of coins and m is the amount of money.

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 1e9);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (i - c >= 0) {
                dp[i] = min(dp[i], 1 + dp[i - c]);
            }
        }
    }

    return dp[amount] == 1e9? -1 : dp[amount];
}

For the problem 279. Perfect Squares, we create a 'dp' vector at the length of n + 1. The 'i+1'_th element represents the minimum number of perfect sequares that sum to 'i'. We iterate through the elements, and update when there is a smaller number of perfect squares, considering all possible combinations. A combination is 1 plus the value of a previous element with the index 'i' minus a perfect square.

int numSquares(int n) {
    vector<int> dp(n + 1, 1e9);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int s = 1; s * s <= i; s++) {
            dp[i] = min(dp[i], 1 + dp[i - s * s]);
        }
    }
    return dp[n] == 1e9? -1 : dp[n];
}

For the problem 2466. Count Ways To Build Good Strings, we create a dp vector with a length of high + 1. The i_th element represents the number of ways to build good strings of length i, so dp[0] = 1 since there is only one good string of length 0. We iterate through the elements and update dp[i] by summing dp[i - zero] and dp[i - one], because we can build this string by adding either zero zeros or one ones to a string of the corresponding length. Finally, the result is calculated by accumulating the values from dp[low] to dp[high].

int countGoodStrings(int low, int high, int zero, int one) {
    const int mod = 1e9+7;
    vector<int> dp(high + 1);
    dp[0] = 1;

    for (int i = 1; i <= high; i++) {
        if (i - zero >= 0)
            dp[i] = (dp[i] + dp[i - zero]) % mod;
        if (i - one >= 0)
            dp[i] = (dp[i] + dp[i - one]) % mod;
    }

    int res = 0;
    for (int i = low; i <= high; i++)
        res = (res + dp[i]) % mod;
    return res;
}

For the problem 1406. Stone Game III, we can use a vector to store the maximum value of stones one can have starting from index i. Therefore, the value at each index is determined by one of the following choices: taking one, two, or three stones, minus the value the other player can have starting from index i + 1, i + 2, or i + 3. If the value starting from index 0 is positive, Alice wins; if it is negative, Bob wins; if it is zero, the game is a tie.

int game(vector<int>& val, int i, vector<int>& mem) {
    if (i >= val.size())
        return 0;

    if (mem[i] != INT_MIN)
        return mem[i];

    int res = val[i] - game(val, i + 1, mem);
    if (i + 1 < val.size())
        res = max(res, val[i] + val[i + 1] - game(val, i + 2, mem));
    if (i + 2 < val.size())
        res = max(res, val[i] + val[i + 1] + val[i + 2] - game(val, i + 3, mem));
    return mem[i] = res;
}
string stoneGameIII(vector<int>& stoneValue) {
    vector<int> mem(stoneValue.size(), INT_MIN);
    int a = game(stoneValue, 0, mem);
    if (a > 0)
        return "Alice";
    else if (a < 0)
        return "Bob";
    else
        return "Tie";
}

In the problem 1048. Longest String Chain, to efficiently check all predecessors, we can store the results of shorter words to avoid redundant checks. First, we sort the words by length. For each word, the length of the chain starts at 1 (as the word itself). We then check all its predecessors - if a predecessor exists, we update the result if chaining to the predecessor results in a longer chain.

int longestStrChain(vector<string>& words) {
    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();
    });

    unordered_map<string, int> mem;
    int maxChain = 0;

    for (const string& word: words) {
        mem[word] = 1;
        for (int i = 0; i < word.size(); i++) {
            string pred = word.substr(0, i) + word.substr(i + 1);
            if (mem.find(pred) != mem.end())
                mem[word] = max(mem[word], 1 + mem[pred]);
        }
        maxChain = max(maxChain, mem[word]);
    }
    return maxChain;
}

For the problem 368. Largest Divisible Subset, we aim to create sets of numbers with a size equal to the length of nums, where each set at a certain index represents the largest divisible subset that includes the number at that index in nums. When adding a new number to a subset, if the new number is larger than all the numbers in the subset, we only need to check whether it is divisible by the largest number in the subset. To simplify this process, we sort nums.

We then iterate through the numbers. For each number, we check all previous subsets. If the largest element of a previous subset is divisible by the current number, we update the current subset's size and previous element accordingly, and track the index of the subset with the maximum size. Finally, the result can be built starting from the tracked index.

vector<int> largestDivisibleSubset(vector<int>& nums) {
    sort(nums.begin(), nums.end());

    int n = nums.size();
    vector<int> setSize(n, 1), preElem(n, -1);
    int maxIdx = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && setSize[j] + 1 > setSize[i]) {
                setSize[i] = setSize[j] + 1;
                preElem[i] = j;
            }
        }
        if (setSize[i] > setSize[maxIdx])
            maxIdx = i;
    }

    vector<int> res;
    for (int i = maxIdx; i != -1; i = preElem[i]) {
        res.push_back(nums[i]);
    }
    return res;
}

In the problem 472. Concatenated Words, we first create a dict hash set to quickly check if a word is in the given list. The brute force solution involves checking all combinations of the words and adding a word to the result if it is in the dict, which results in a time complexity of O(2ⁿ) (where n is the length of the word list).

A more efficient approach is to, for each word in the list, check all its prefixes. If the corresponding suffix is in the dict or if the suffix can be recursively concatenated with other given words, we add the word to the result. The memoization technique is helpful here to avoid repeatedly checking the same strings. Note that when checking a word, we start with a prefix of length 1 and end with a suffix of length 1 to prevent adding words that are not concatenations.

bool check(string& word, unordered_set<string>& dict, unordered_map<string, bool>& mem) {
    int m = word.size();
    if (mem.find(word) != mem.end())
        return mem[word];

    for (int i = 1; i < m; i++) {
        string prefix = word.substr(0, i);
        string suffix = word.substr(i);
        if (dict.find(prefix) == dict.end())
            continue;
        if (dict.find(suffix) != dict.end() || check(suffix, dict, mem)) {
            mem[word] = true;
            return true;
        }
    }
    mem[word] = false;
    return false;
}

vector<string> findAllConcatenatedWordsInDict(vector<string>& words) {
    unordered_set<string> dict(words.begin(), words.end());
    unordered_map<string, bool> mem;
    vector<string> res;
    for (string& word: words) {
        if (check(word, dict, mem))
            res.push_back(word);
    }
    return res;
}

For complex questions where it is difficult to come up with the optimal solution immediately, it helps to solve the problem step by step: starting with a recursive approach, then adding memoization, followed by tabulation, and finally optimizing for space. For example, in 518. Coin Change II, the following is the brute force recursive solution.

We introduce the helper function changeRec(), where i is the index in the coins array. The base cases are:

To have an amount of 0 dollars, there is exactly one way - by not using any coins.
When trying with a coin index out of range, there is no way to achieve the amount of money.

For each coin at index i, we have two choices: to include or exclude this coin in a combination. The number of ways to include this coin in the combination for an amount is equal to the number of ways for the amount minus the value of this coin, because we can add one coin to that amount to form the current amount. The number of ways to exclude this coin is equal to the number of ways for the same amount with the index incremented by 1.

int changeRec(int amount, vector<int>& coins, int i) {
    if (amount == 0)
        return 1;
    if (i >= coins.size())
        return 0;

    int inc = 0;
    if (coins[i] <= amount)
        inc = changeRec(amount - coins[i], coins, i);
    int exc = changeRec(amount, coins, i + 1);

    return inc + exc;
}

int change(int amount, vector<int>& coins) {
    return changeRec(amount, coins, 0);
}

We can use memoization to save time by storing the results of calculations for the same amount of money and indices of coins, avoiding redundant computations.

int changeMem(int amount, vector<int>& coins, int i, vector<vector<int>>& mem) {
    if (amount == 0)
        return 1;
    if (i >= coins.size())
        return 0;

    if (mem[i][amount] != -1)
        return mem[i][amount];

    int inc = 0;
    if (coins[i] <= amount)
        inc = changeMem(amount - coins[i], coins, i, mem);
    int exc = changeMem(amount, coins, i + 1, mem);

    return mem[i][amount] = inc + exc;
}

int change(int amount, vector<int>& coins) {
    vector<vector<int>> mem(coins.size() + 1, vector<int>(amount + 1, -1));
    return changeMem(amount, coins, 0, mem);
}

We follow a similar logic for the tabulation solution. The first column values are all 1, as there is one way to achieve an amount of 0. The first row contains the number of ways to combine the amount using only the first coin, so for amounts that are multiples of this coin's value, the number of ways is 1. Starting from the second row, each row represents the inclusion of one more different coin. For each amount, the number of ways is the sum of:

The number of ways (exc) to achieve the same amount in the previous row (excluding the current coin).
The number of ways (inc) to achieve the amount minus the current coin's value in the current row (including the current coin).

int change(int amount, vector<int>& coins) {
    int n = coins.size();
    vector<vector<int>> dp(n, vector<int>(amount + 1));

    for (int i = 0; i < n; i++)
        dp[i][0] = 1;

    for (int a = 0; a <= amount; a += coins[0])
        dp[0][a] = 1;

    for (int i = 1; i < n; i++) {
        int c = coins[i];

        for (int a = 1; a <= amount; a++) {
            if (a - c < 0)
                dp[i][a] = dp[i - 1][a];
            else
                dp[i][a] = dp[i - 1][a] + dp[i][a - c];
        }
    }
    return dp[n - 1][amount];
}

The time complexity is O(n * m), where n is the number of coins and m is the amount of money. The space complexity is O(n * m) for the dp table. After analyzing the logic, we can further optimize the space to O(m) because each calculation only references the value in the previous row for the same amount.

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1);

    for (int a = 0; a <= amount; a += coins[0])
        dp[a] = 1;

    for (int i = 1; i < coins.size(); i++) {
        int c = coins[i];

        for (int a = 1; a <= amount; a++) {
            if (a - c >= 0)
                dp[a] += dp[a - c];
        }
    }
    return dp[amount];
}

Similarily for the problem 1143. Longest Common Subsequence, the recursive solution is as follows. We introduce a helper function lcsR(), which takes two strings and their corresponding indices. Each time, we calculate the longest common subsequence starting from index i and j. We may either skip the i_th character in the first string or skip the j_th character in the second string. If the i_th character in the first string is equal to the j_th character in the second string, we also compare the length of 1 plus the LCS from the next indices.

int lcsR(string s, string t, int i, int j) {
    if (i >= s.length() || j >= t.length())
        return 0;

    int inc = 0;
    if (s[i] == t[j])
        inc = 1 + lcsR(s, t, i + 1, j + 1);

    int exc = max(lcsR(s, t, i + 1, j),
                  lcsR(s, t, i,     j + 1));

    return max(exc, inc);
}

int longestCommonSubsequence(string text1, string text2) {
    return lcsR(text1, text2, 0, 0);
}

Then, we create a 2D vector to store the LCS values at each i and j, saving time by avoiding repeated calculations.

int lcsM(string s, string t, int i, int j, vector<vector<int>>& mem) {
    if (i >= s.length() || j >= t.length())
        return 0;
    if (mem[i][j] != -1)
        return mem[i][j];

    int inc = 0;
    if (s[i] == t[j])
        inc = 1 + lcsR(s, t, i + 1, j + 1);

    int exc = max(lcsR(s, t, i + 1, j),
                  lcsR(s, t, i,     j + 1));

    return mem[i][j] = max(exc, inc);
}

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.length(), m = text2.length();
    vector<vector<int>> mem(n, vector<int>(m, -1));
    return lcsM(text1, text2, 0, 0, mem);
}

In the tabulation solution, we traverse both strings backward. Each time, if the characters are the same, we add 1 for the common character and the LCS from the next indices of both strings. Otherwise, we compare the LCS of skipping the i_th character in text1 with the LCS of skipping the j_th character in text2.

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.length(), m = text2.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (text1[i] == text2[j])
                dp[i][j] = 1 + dp[i + 1][j + 1];
            else
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
        }
    }
    return dp[0][0];
}

The time complexity is O(n * m) for the two loops, where n and m are the lengths of the two strings. The space complexity is O(n * m) for the dp table. We can further optimize the space to O(m) by reusing two vectors repeatedly. We store the current row in r, with the value being either 0 or 1. When needing to reference the other row, the row index will be 1 - r.

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.length(), m = text2.length();
    vector<vector<int>> dp(2, vector<int>(m + 1));

    int r = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (text1[i] == text2[j])
                dp[r][j] = 1 + dp[1 - r][j + 1];
            else
                dp[r][j] = max(dp[1 - r][j], dp[r][j + 1]);
        }
        r = 1 - r;
    }
    return dp[1 - r][0];
}

For the problem 309. Best Time to Buy and Sell Stock with Cooldown, we introduce two variables in the helper function to calculate the maximum profit that can be earned starting from the i_th day, either holding a stock or not holding any stock.

If holding a stock: The profit can be either from buying a stock or doing nothing on the i_th day. Doing nothing means that the profit is the same as the one starting from the next day (i + 1). Buying a stock means that the profit is equal to the one starting from the next day minus the stock price today.
If not holding a stock: The profit can be either from selling a stock or doing nothing. Since there is a 1-day cooldown, the profit from selling a stock is equal to the one starting from the day after the next (i + 2), plus the stock price today.

int maxProfitR(vector<int>& prices, int i, bool hold) {
    if (i >= prices.size())
        return 0;

    if (!hold) {
        return max(maxProfitR(prices, i + 1, true) - prices[i],  // buy
                   maxProfitR(prices, i + 1, hold));             // skip
    }
    else {
        return max(maxProfitR(prices, i + 2, false) + prices[i], // sell
                   maxProfitR(prices, i + 1, hold));             // skip
    }
}

int maxProfit(vector<int>& prices) {
    return maxProfitR(prices, 0, false);
}

Then, we store the maximum profits in a table to save time by avoiding repeated calculations.

int maxProfitM(vector<int>& prices, int i, int hold, vector<vector<int>>& mem) {
    if (i >= prices.size())
        return 0;

    if (mem[hold][i] != -1)
        return mem[hold][i];

    if (!hold) {
        return mem[hold][i] =
                max(maxProfitM(prices, i + 1, 1, mem) - prices[i],
                    maxProfitM(prices, i + 1, hold, mem));
    }
    else {
        return mem[hold][i] =
                max(maxProfitM(prices, i + 2, 0, mem) + prices[i],
                    maxProfitM(prices, i + 1, hold, mem));
    }
}

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> mem(2, vector<int>(n, -1));
    return maxProfitM(prices, 0, 0, mem);
}

In the tabulation approach, we use two vectors: buy and sell. The i+1_th element in buy represents the maximum profit from buying a stock on the i_th day, and the i+1_th element in sell represents the maximum profit from selling a stock on the i_th day.

On each day, the maximum buying profit is either:
1. Doing nothing (buy[i]): the same buying profit as the previous day.
2. Buying a stock (-prices[i]): paying the stock price on the i_th day while not holding any stock (sell[i]: sold on the i-1-th day and not holding a stock).
The maximum selling profit is either:
1. Doing nothing (sell[i]): the same selling profit as the previous day.
2. Selling a stock (+prices[i]): earning the stock price on the i-th day while holding a stock for 2 days (buy[i - 1]: bought on the i-2_th day and holding a stock).

We start the loop from 1 to simplify the logic, avoiding the need to check if i - 1 is out of the range of the vector. The best profit from selling on the first day is 0, and the best profit from buying on the first day is the negative value of the stock price on the first day.

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<int> buy(n + 1);
    vector<int> sell(n + 1);

    buy[1] = -prices[0];
    for (int i = 1; i < n; i++) {
        buy[i + 1] = max(buy[i], sell[i] - prices[i]);
        sell[i + 1] = max(sell[i], buy[i - 1] + prices[i]);
    }
    return sell[n];
}

In the following problems, I will provide the tabulation approach directly and leave the other methods for readers to practice.

For the problem 1035. Uncrossed Lines, we use a 2D table following similar logic. At the indices where the numbers are equal, the maximum number of uncrossed lines is increased by 1 from the previous value. Otherwise, we take the maximum value considering one more number in either vector. The time complexity is O(n * m). The space complexity is also O(n * m), and it can be improved to O(m) as follows.

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size(), m = nums2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (nums1[i] == nums2[j])
                dp[i + 1][j + 1] = 1 + dp[i][j];
            else
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
        }
    }
    return dp[n][m];
}

int maxUncrossedLinesOpt(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size(), m = nums2.size();
    vector<vector<int>> dp(2, vector<int>(m + 1));

    int r = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (nums1[i] == nums2[j])
                dp[r][j + 1] = 1 + dp[1 - r][j];
            else
                dp[r][j + 1] = max(dp[1 - r][j + 1], dp[r][j]);
        }
        r = 1 - r;
    }
    return dp[1 - r][m];
}

In the problem 10. Regular Expression Matching, an element in dp stores whether the strings match at the corresponding indices. Thus, the base case at the end of both strings (dp[n][m]) is true.

In the loop, we first check for '*'. If the next character in p is '*', we have two choices:

Skip the j-th character in p (where '*' means zero occurrences of the preceding character).
Advance the index in s (where '*' means one or more occurrences of the preceding character).

Then, we check if there is a match (either a '.' is found in p, or both characters are the same), and advance both indices.

Note that the outer loop starts with n to cover cases where '*' is the last character in p and there are one or multiple occurrences of the preceding character at the end of s.

bool isMatch(string s, string p) {
    int n = s.size(), m = p.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
    dp[n][m] = true;

    for (int i = n; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            bool match = i < n && (p[j] == '.' || s[i] == p[j]);

            if (j + 1 < m && p[j + 1] == '*') {
                // to use '*' or not to use '*'
                dp[i][j] = dp[i][j + 2] || (match && dp[i + 1][j]);
            }
            else if (match) {
                dp[i][j] = dp[i + 1][j + 1];
            }
        }
    }

    return dp[0][0];
}

I hope this article have helped you understand Dynamic Programming better. If you are interested in practicing more problem solving, please check out LeetCode - Dynamic Programming tag.

8 References

Author: Winfred Lu

Created: 2024-08-05 Mon 11:46

Validate

Winfred C. H. Lu

Sunday, August 4, 2024