Dynamic Programming Common Patterns and Code Template

This article is an advanced version of my previous Detailed Explanation of Dynamic Programming which received over 200 likes. I have added more valuable content, hoping this article becomes a "guideline" for solving dynamic programming problems.

Dynamic Programming (DP) problems can be quite challenging for many readers, but they are also the most intriguing and skillful. This book dedicates an entire chapter to this algorithm, highlighting its significance.

This article addresses several questions:

What is dynamic programming? What techniques are there for solving dynamic programming problems? How can one learn dynamic programming?

After solving many problems, you'll realize there are only a few common techniques in algorithms. The subsequent chapters of our dynamic programming series all use the problem-solving framework introduced here. Once you understand this framework, solving these problems becomes much easier. Therefore, this article is placed in the first chapter, aiming to be a guideline for solving dynamic programming problems. Let's dive into the details.

First of all, the general form of dynamic programming problems is to find the optimal value. Dynamic programming is actually an optimization method from operations research, frequently applied in computer problems, such as finding the longest increasing subsequence, the minimum edit distance, etc.

Since we are looking for the optimal value, what is the core issue? The core issue in solving dynamic programming problems is exhaustive enumeration. Because to find the optimal value, we must enumerate all possible answers and then find the best one.

Is dynamic programming really that simple, just exhaustive enumeration? But the dynamic programming problems I see are very difficult!

Firstly, while the core idea of dynamic programming is to exhaustively search for the optimal value, problems can vary greatly. Exhausting all feasible solutions is not easy and requires a熟练 grasp of recursive thinking. Only by listing the correct "state transition equation" can you correctly exhaust all possibilities. Moreover, you need to determine if the algorithm problem has the "optimal substructure", meaning whether the optimal value of the subproblems can lead to the optimal value of the original problem. Additionally, dynamic programming problems have "overlapping subproblems", and brute-force exhaustion would be inefficient. Therefore, you need to use a "memoization" or "DP table" to optimize the exhaustive process and avoid unnecessary calculations.

The overlapping subproblems, optimal substructure, and state transition equation mentioned above are the three key elements of dynamic programming. I will explain what these mean with examples shortly. However, in actual algorithm problems, writing the state transition equation is the most challenging part, which is why many people find dynamic programming difficult. I will provide a thought framework I have summarized to help you think through the state transition equation:

Clarify the "state" -> Clarify the "choices" -> Define the meaning of the dp array/function.

Following this approach, the final solution code will fit into the following framework:

# top-down recursive dynamic programming
def dp(state1, state2, ...):
    for choice in all_possible_choices:
        # the state has changed due to the choice made
        result = find_optimal(result, dp(state1, state2, ...))
    return result

# bottom-up iterative dynamic programming
# initialize the base case
dp[0][0][...] = base case
# perform state transition
for state1 in all_values_of_state1:
    for state2 in all_values_of_state2:
        for ...
            dp[state1][state2][...] = find_optimal(choice1, choice2, ...)

The following explains the basic principles of dynamic programming through the Fibonacci sequence problem and the coin change problem. The former is mainly to help you understand what overlapping subproblems are (the Fibonacci sequence does not involve finding an optimum, so strictly speaking, it is not a dynamic programming problem). The latter focuses on how to formulate the state transition equation.

1. Fibonacci Sequence

LeetCode problem 509, "Fibonacci Number," illustrates this issue. Do not dismiss this example as too simple. Only simple examples allow you to fully concentrate on the general ideas and techniques behind the algorithm without being confused by obscure details. If you want more challenging examples, there are plenty in the upcoming dynamic programming series.

Brute-Force Recursion

The mathematical form of the Fibonacci sequence is recursive, and the code can be written as follows:

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

def fib(N: int) -> int:
    if N == 1 or N == 2:
        return 1
    return fib(N - 1) + fib(N - 2)

// fib calculates the N-th term of the Fibonacci sequence
func fib(N int) int {
    if N == 1 || N == 2 {
        return 1
    }
    return fib(N-1) + fib(N-2)
}

var fib = function(N) {
    if (N === 1 || N === 2) return 1;
    return fib(N - 1) + fib(N - 2);
};

This topic needs little introduction, as it's often the go-to example when teachers explain recursion. We know that while this code is straightforward and easy to understand, it is highly inefficient. But why exactly is it inefficient? Suppose n = 20; let's draw the recursion tree:

How do we interpret this recursion tree? To calculate the original problem f(20), we must first compute the subproblems f(19) and f(18). To compute f(19), we need to first solve f(18) and f(17), and so on. Finally, when we reach f(1) or f(2), the results are known, and the recursion tree stops growing downward.

How do we calculate the time complexity of a recursive algorithm? By multiplying the number of subproblems by the time required to solve one subproblem.

First, calculate the number of subproblems, which is the total number of nodes in the recursion tree. Clearly, the total number of nodes in a binary tree is exponential, so the number of subproblems is O(2^n).

Next, calculate the time to solve one subproblem. In this algorithm, there are no loops, only the addition operation f(n - 1) + f(n - 2), which takes O(1) time.

Therefore, the time complexity of this algorithm is the product of the two, which is O(2^n), an exponential level, which is explosive.

Observing the recursion tree, we clearly see the cause of inefficiency: there are many repeated calculations. For example, f(18) is computed twice, and you can see that the recursion tree rooted at f(18) is enormous, so recalculating it wastes a lot of time. Moreover, f(18) is not the only node being recalculated, making this algorithm extremely inefficient.

This is the first characteristic of dynamic programming problems: overlapping subproblems. Next, we will find a way to solve this issue.

Recursive Solution with Memoization

Understanding the problem is already half the battle. Since the main issue is redundant calculations, we can create a "memo" to store answers. After solving a subproblem, instead of immediately returning the result, we first record it in the memo. Whenever we encounter a subproblem, we check the memo first. If we find that the problem has already been solved, we simply use the stored answer instead of recalculating.

Typically, an array is used as this memo, but you could also use a hash table (dictionary). The concept remains the same.

int fib(int N) {
    // initialize the memo array to all zeros
    int[] memo = new int[N + 1];
    // perform recursion with memoization
    return dp(memo, N);
}

// perform recursion with memoization
int dp(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // already calculated, no need to calculate again
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

int fib(int N) {
    // initialize the memoization array to all 0s
    vector<int> memo(N + 1, 0);
    // perform recursion with memoization
    return dp(memo, N);
}

// perform recursion with memoization
int dp(vector<int>& memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // already calculated, no need to recalculate
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

def fib(N: int) -> int:
    # initialize the memoization array to 0
    memo = [0] * (N + 1)
    # perform recursion with memoization
    return dp(memo, N)

# perform recursion with memoization
def dp(memo: List[int], n: int) -> int:
    # base case
    if n == 0 or n == 1: return n
    # already calculated, no need to calculate again
    if memo[n] != 0: return memo[n]
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2)
    return memo[n]

func fib(N int) int {
    // initialize the memoization array to all 0s
    memo := make([]int, N+1)
    // perform recursion with memoization
    return dp(memo, N)
}

// perform recursion with memoization
func dp(memo []int, n int) int {
    // base case
    if n == 0 || n == 1 {
        return n
    }
    // already calculated, no need to compute again
    if memo[n] != 0 {
        return memo[n]
    }
    memo[n] = dp(memo, n-1) + dp(memo, n-2)
    return memo[n]
}

var fib = function(N) {
    // Initialize the memo array with all zeros
    let memo = new Array(N + 1).fill(0);
    // Perform recursion with memoization
    return dp(memo, N);
};

// Recurse with memoization
var dp = function(memo, n) {
    // base case
    if (n == 0 || n == 1) return n;
    // Already calculated, no need to compute again
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
};

Now, draw the recursion tree, and you will understand what the "memoization" actually does.

In fact, the recursive algorithm with "memoization" transforms a recursion tree, which contains a large amount of redundancy, into a recursion graph without redundancy by "pruning". This significantly reduces the number of subproblems (i.e., nodes in the recursion graph).

How do you calculate the time complexity of a recursive algorithm? It's the number of subproblems multiplied by the time needed to solve one subproblem.

The number of subproblems, i.e., the total number of nodes in the graph, is proportional to the input size n = 20, as the algorithm avoids redundant calculations. The subproblems are f(1), f(2), f(3) ... f(20), so the number of subproblems is O(n).

The time to solve one subproblem is O(1), as there are no loops involved.

Therefore, the time complexity of this algorithm is O(n), which is a significant improvement over the brute-force algorithm.

At this point, the efficiency of the recursive solution with memoization is the same as that of the iterative dynamic programming solution. In fact, this approach is very similar to the common dynamic programming solutions, except that it solves problems "top-down" using recursion, whereas the more common dynamic programming code solves problems "bottom-up" using iteration.

What does "top-down" mean? Notice the recursive tree (or graph) we drew earlier, which extends from top to bottom. It starts from a larger problem, such as f(20), and gradually breaks it down into smaller problems until it reaches the base cases f(1) and f(2). Then, it returns the answers layer by layer. This is what we call "top-down."

What does "bottom-up" mean? Conversely, we start from the bottom, the simplest, smallest-scale problems with known results, f(1) and f(2) (base cases), and work our way up until we reach the desired answer f(20). This is the idea behind "iteration," and it's why dynamic programming typically avoids recursion and relies on loop iterations for computation.

Iterative (Recursive) Solution Using the dp Array

Inspired by the previous step of using a "memoization" table, we can separate this "memoization" into an independent table, commonly known as the DP table. Wouldn't it be great to perform "bottom-up" calculations on this table!

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // state transition
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

int fib(int N) {
    if (N == 0) return 0;
    vector<int> dp(N + 1);
    // base case
    dp[0] = 0; dp[1] = 1;
    // state transition
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

def fib(N: int) -> int:
    if N == 0:
        return 0
    dp = [0] * (N + 1)
    # base case
    dp[0] = 0
    dp[1] = 1
    # state transition
    for i in range(2, N + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[N]

func fib(N int) int {
    if N == 0 {
        return 0
    }
    dp := make([]int, N+1)
    // base case
    dp[0], dp[1] = 0, 1
    // state transition
    for i := 2; i <= N; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }

    return dp[N]
}

var fib = function(N) {
    if (N === 0) return 0;
    let dp = new Array(N + 1).fill(0);
    // base case
    dp[0] = 0; dp[1] = 1;
    // state transition
    for (let i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
};

A diagram makes it much easier to understand, and you might notice that this DP table closely resembles the result after "pruning" from before, only calculated in reverse:

In fact, the "memo" array in the recursive solution with memoization, once completed, is the same as the dp array in this approach. By comparing the execution process of the two algorithms in the visual panel, you can more intuitively see their connection.

Therefore, the top-down and bottom-up approaches are essentially similar, and in most cases, their efficiency is nearly the same.

Further Insights

Here, we introduce the term "state transition equation," which is essentially a mathematical form describing the structure of a problem:

Why is it called a "state transition equation"? Simply to sound sophisticated.

The function parameter f(n) continuously changes, so you can think of the parameter n as a state. This state n is derived (by addition) from the states n - 1 and n - 2, which is what we call state transition. That's all there is to it.

You will notice that all operations in the solutions above, such as return f(n - 1) + f(n - 2), dp[i] = dp[i - 1] + dp[i - 2], and the initialization of memoization or the DP table, revolve around different expressions of this equation.

This illustrates the importance of establishing a "state transition equation" as it is the core of solving the problem. It is also easy to see that the state transition equation directly represents the brute-force solution.

Do not underestimate brute-force solutions; the hardest part of dynamic programming problems is writing this brute-force solution, which is the state transition equation.

Once you write the brute-force solution, optimization is merely a matter of using a memoization or a DP table, with no additional mysteries.

At the end of this example, let's discuss a detail for optimization.

Observant readers will notice that, according to the Fibonacci sequence's state transition equation, the current state n is only related to the two previous states, n-1 and n-2. Thus, it is unnecessary to store all states in a long DP table; you only need to store the previous two states.

Therefore, you can further optimize to reduce the space complexity to O(1). This leads to the most common algorithm for calculating Fibonacci numbers:

int fib(int n) {
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // represent dp[i - 1] and dp[i - 2] respectively
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2;
        // rolling update
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

int fib(int n) {
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // represent dp[i - 1] and dp[i - 2] respectively
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2;
        // rolling update
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

def fib(n: int) -> int:
    if n == 0 or n == 1:
        # base case
        return n
    # represent dp[i - 1] and dp[i - 2] respectively
    dp_i_1, dp_i_2 = 1, 0
    for i in range(2, n + 1):
        # dp[i] = dp[i - 1] + dp[i - 2];
        dp_i = dp_i_1 + dp_i_2
        # rolling update
        dp_i_2 = dp_i_1
        dp_i_1 = dp_i
    return dp_i_1

func fib(n int) int {
    if n == 0 || n == 1 {
        // base case
        return n
    }
    // represent dp[i - 1] and dp[i - 2] respectively
    dp_i_1, dp_i_2 := 1, 0
    for i := 2; i <= n; i++ {
        // dp[i] = dp[i - 1] + dp[i - 2];
        dp_i := dp_i_1 + dp_i_2
        // rolling update
        dp_i_2 = dp_i_1
        dp_i_1 = dp_i
    }
    return dp_i_1
}

var fib = function(n) {
    if (n === 0 || n === 1) {
        // base case
        return n;
    }
    // represent dp[i - 1] and dp[i - 2] respectively
    let dp_i_1 = 1, dp_i_2 = 0;
    for (let i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        let dp_i = dp_i_1 + dp_i_2;
        // rolling update
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
};

This is usually the final optimization step for dynamic programming problems. If we find that each state transition only requires a part of the DP table, we can try to reduce the size of the DP table and only record necessary data, thereby reducing the space complexity.

The example above effectively reduces the size of the DP table from n to 2, which means the space complexity is reduced by an order of magnitude. I will further explain this technique of compressing space complexity in the following article Dimensionality Reduction for Dynamic Programming. Generally, this is used to compress a two-dimensional DP table into one dimension, reducing the space complexity from O(n^2) to O(n).

Some might ask, what about the other important feature of dynamic programming, "optimal substructure"? This will be covered next. The Fibonacci sequence example is not strictly a dynamic programming problem because it does not involve finding the maximum or minimum value. The purpose of the example was to illustrate the method of eliminating overlapping subproblems and to demonstrate the process of refining solutions to obtain the optimal one. Now, let's look at the second example, the coin change problem.

II. Coin Change Problem

This is LeetCode problem #322 "Coin Change":

Given k types of coins with denominations c1, c2 ... ck, and an infinite supply of each type, along with a total amount amount, the task is to find the minimum number of coins needed to make up that amount. If it is not possible to make up the amount, the algorithm should return -1. The function signature of the algorithm is as follows:

// `coins` contains the denominations of available coins, and `amount` is the target amount
int coinChange(int[] coins, int amount);

// coins contains the denominations of available coins, and amount is the target amount
int coinChange(vector<int>& coins, int amount);

# coins contains the denominations of available coins, amount is the target amount
def coinChange(coins: List[int], amount: int) -> int:

// coins contains the denominations of available coins, and amount is the target amount
func coinChange(coins []int, amount int) int {}

var coinChange = function(coins, amount) {}

For example, if k = 3 with coin denominations of 1, 2, and 5, and the total amount amount = 11, you need at least 3 coins to make up the amount, i.e., 11 = 5 + 5 + 1.

How do you think a computer should solve this problem? Obviously, it involves listing all possible ways to combine the coins and then finding the minimum number of coins needed.

Brute Force Recursion

Firstly, this problem is a dynamic programming problem because it has the "optimal substructure" property. For a problem to have an "optimal substructure," its subproblems must be independent of each other. What does it mean to be independent? You probably don't want to see a mathematical proof, so I'll explain with a simple example.

Imagine you are taking an exam where each subject's score is independent of the others. Your main goal is to achieve the highest total score. Your subproblems would be to score the highest in each subject, like Chinese, Math, etc. To score the highest in each subject, you need to maximize your scores in multiple-choice questions, fill-in-the-blank questions, and so on. Ultimately, if you score full marks in each subject, you achieve the highest total score.

This process gives the correct result: the highest total score is the sum of the individual scores. This works because the process follows the optimal substructure, where the subproblems of scoring the highest in each subject are independent and do not interfere with each other.

However, if we add a condition where your Chinese and Math scores are interdependent, meaning you cannot score full marks in both simultaneously (if your Math score is high, your Chinese score decreases, and vice versa), then the highest total score you can achieve will not be the sum of the individual maximum scores. Following the previous approach would lead to an incorrect result. This is because the subproblems of scoring the highest in each subject are not independent; the scores in Chinese and Math affect each other, preventing simultaneous optimization, thus breaking the optimal substructure.

Returning to the coin change problem, why does it have an optimal substructure? Suppose you have coins of denominations 1, 2, 5 and you want to find the minimum number of coins needed for amount = 11 (the main problem). If you know the minimum number of coins needed for amount = 10, 9, 6 (subproblems), you just need to add one more coin (of denominations 1, 2, 5) to each subproblem's solution and take the minimum of these values to get the main problem's solution. Since there is no limit to the number of coins, the subproblems are independent of each other.

So, now that we know this is a dynamic programming problem, how do we formulate the correct state transition equation?

1. Determine the 'state', which is the variable that changes in both the original problem and subproblems. Since the number of coins is unlimited and the denominations are given, only the target amount keeps approaching the base case. Therefore, the only 'state' is the target amount amount.

2. Determine the 'choices', which are the actions that cause the 'state' to change. The target amount changes because you are choosing coins. Each coin you choose reduces the target amount. Thus, all coin denominations are your 'choices'.

3. Define the dp function/array clearly. Here, we are discussing a top-down approach, so there will be a recursive dp function. Generally, the function's parameters are the variables that change during state transitions, i.e., the 'state' mentioned earlier; the function's return value is what the problem asks us to calculate. For this problem, there is only one state, the 'target amount', and the problem asks us to find the minimum number of coins needed to make up the target amount.

Thus, we can define the dp function as follows: dp(n) represents, given a target amount n, it returns the minimum number of coins needed to make up the target amount n.

Based on this definition, our final answer is the return value of dp(amount).

Once you understand these key points, you can write the pseudocode for the solution:

// Pseudocode framework
int coinChange(int[] coins, int amount) {
    // The final result required by the problem is dp(amount)
    return dp(coins, amount);
}

// Definition: To make up the amount n, at least dp(coins, n) coins are needed
int dp(int[] coins, int n) {
    // Make a choice, choose the result that requires the fewest coins
    for (int coin : coins) {
        res = min(res, 1 + dp(coins, n - coin));
    }
    return res;
}

// Pseudocode framework
int coinChange(vector<int>& coins, int amount) {
    // The final result required by the problem is dp(amount)
    return dp(coins, amount);
}

// Definition: To make up the amount n, at least dp(coins, n) coins are needed
int dp(vector<int>& coins, int n) {
    // Make a choice, choose the result that requires the fewest coins
    int res = INT_MAX;
    for (const int coin : coins) {
        res = min(res, subProb + 1);
    }
    return res;
}

# Pseudocode framework
def coinChange(coins: List[int], amount: int) -> int:
    # The final result required by the problem is dp(amount)
    return dp(coins, amount)

# Definition: To make up the amount n, at least dp(coins, n) coins are needed
def dp(coins: List[int], n: int) -> int:
    # Make a choice, choose the result that requires the fewest coins
    # Initialize res to positive infinity
    res = float('inf')
    for coin in coins:
        res = min(res, sub_problem + 1)
    return res

// Pseudocode framework
func coinChange(coins []int, amount int) int {
    // The final result required by the problem is dp(amount)
    return dp(coins, amount)
}

// Definition: To make up the amount n, at least dp(coins, n) coins are needed
func dp(coins []int, n int) int {
    // Initialize to the maximum value
    res := math.MaxInt32
    
    // Make a choice, choose the result that requires the fewest coins
    for _, coin := range coins {
        res = min(res, 1+subProblem)
    }
    return res
}

// Pseudocode framework
var coinChange = function(coins, amount) {
    // The final result required by the problem is dp(amount)
    return dp(coins, amount);
}

// Definition: To make up the amount n, at least dp(coins, n) coins are needed
var dp = function(coins, n) {
    // Initialize to the maximum value
    let res = Infinity;
    
    // Make a choice, choose the result that requires the fewest coins
    for (let coin of coins) {
        res = Math.min(res, 1 + subProblem);
    }
    return res;
};

According to the pseudocode, we add the base case to get the final answer. Clearly, when the target amount is 0, the number of coins needed is 0; when the target amount is less than 0, there is no solution, and we return -1:

class Solution {
    public int coinChange(int[] coins, int amount) {
        // the final result required by the problem is dp(amount)
        return dp(coins, amount);
    }

    // definition: to make up the amount n, at least dp(coins, n) coins are needed
    int dp(int[] coins, int amount) {
        // base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            // calculate the result of the subproblem
            int subProblem = dp(coins, amount - coin);
            // skip if the subproblem has no solution
            if (subProblem == -1) continue;
            // choose the optimal solution from the subproblem, then add one
            res = Math.min(res, subProblem + 1);
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // the final result required by the problem is dp(amount)
        return dp(coins, amount);
    }

private:
    // definition: to make up the amount n, at least dp(coins, n) coins are needed
    int dp(vector<int>& coins, int amount) {
        // base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        int res = INT_MAX;
        for (int coin : coins) {
            // calculate the result of the subproblem
            int subProblem = dp(coins, amount - coin);
            // skip if the subproblem has no solution
            if (subProblem == -1) continue;
            // choose the optimal solution in the subproblem, then add one
            res = min(res, subProblem + 1);
        }

        return res == INT_MAX ? -1 : res;
    }
};

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # the final result required by the problem is dp(amount)
        return self.dp(coins, amount)

    # definition: to make up the amount n, at least dp(coins, n) coins are needed
    def dp(self, coins, amount):
        # base case
        if amount == 0: 
            return 0
        if amount < 0: 
            return -1

        res = float('inf')
        for coin in coins:
            # calculate the result of the subproblem
            subProblem = self.dp(coins, amount - coin)
            # skip if the subproblem has no solution
            if subProblem == -1: 
                continue
            # choose the optimal solution in the subproblem, then add one
            res = min(res, subProblem + 1)

        return res if res != float('inf') else -1

func coinChange(coins []int, amount int) int {
    // The final result required by the problem is dp(amount)
    return dp(coins, amount)
}

// Definition: To make up the amount n, at least dp(coins, n) coins are needed
func dp(coins []int, amount int) int {
    // base case
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }

    res := math.MaxInt32
    for _, coin := range coins {
        // Calculate the result of the subproblem
        subProblem := dp(coins, amount - coin)
        // Skip if the subproblem has no solution
        if subProblem == -1 {
            continue
        }
        // Choose the optimal solution in the subproblem, then add one
        res = min(res, subProblem + 1)
    }

    if res == math.MaxInt32 {
        return -1
    }
    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

var coinChange = function(coins, amount) {
    // The final result required by the problem is dp(amount)
    return dp(coins, amount);
}

// Definition: To make up the amount n, at least dp(coins, n) coins are needed
function dp(coins, amount) {
    // base case
    if (amount === 0) return 0;
    if (amount < 0) return -1;

    let res = Number.MAX_SAFE_INTEGER;
    for (let coin of coins) {
        // Calculate the result of the subproblem
        let subProblem = dp(coins, amount - coin);
        // Skip if the subproblem has no solution
        if (subProblem === -1) continue;
        // Choose the optimal solution in the subproblem, then add one
        res = Math.min(res, subProblem + 1);
    }

    return res === Number.MAX_SAFE_INTEGER ? -1 : res;
}

At this point, the state transition equation is complete, and the above algorithm is already a brute-force solution. The mathematical form of the above code is the state transition equation:

Thus, this problem is essentially solved, though overlapping sub-problems need to be eliminated. For example, consider the recursive tree for amount = 11, coins = {1,2,5}:

Time complexity analysis of the recursive algorithm: total number of sub-problems x time required to solve each sub-problem.

The total number of sub-problems corresponds to the number of nodes in the recursive tree. However, the algorithm will perform pruning, which depends on the specific coin denominations given in the problem. Therefore, the tree grows irregularly, making it difficult to precisely calculate the number of nodes on the tree. In such cases, we generally estimate an upper bound on the time complexity based on the worst-case scenario.

Assuming the target amount is n, and the number of given coins is k, the height of the recursive tree in the worst case is n (using coins with a denomination of 1). Then, assuming this is a full k-ary tree, the total number of nodes is of the order k^n.

Next, consider the complexity of each sub-problem. Since each recursion includes a for loop, the complexity is $O(k)$, resulting in a total time complexity of $O(k^n)$, which is exponential.

Recursive with Memoization

Similar to the previous Fibonacci sequence example, a slight modification can eliminate sub-problems through memoization:

class Solution {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        // Initialize the memo with a special value that
        // won't be picked, representing it has not been
        Arrays.fill(memo, -666);

        return dp(coins, amount);
    }

    int dp(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        // Check the memo to prevent repeated calculations
        if (memo[amount] != -666)
            return memo[amount];

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            // Calculate the result of the subproblem
            int subProblem = dp(coins, amount - coin);

            // Skip if the subproblem has no solution
            if (subProblem == -1) continue;
            // Choose the optimal solution in the subproblem, then add one
            res = Math.min(res, subProblem + 1);
        }
        // Store the calculation result in the memo
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}

class Solution {
public:
    vector<int> memo;
    
    int coinChange(vector<int>& coins, int amount) {
        memo = vector<int> (amount + 1, -666);
        // Initialize the memo with a special value that
        // won't be picked, representing it has not been
        return dp(coins, amount);
    }

    int dp(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        // Check the memo to prevent repeated calculations
        if (memo[amount] != -666)
            return memo[amount];

        int res = INT_MAX;
        for (int coin : coins) {
            // Calculate the result of the subproblem
            int subProblem = dp(coins, amount - coin);

            // Skip if the subproblem has no solution
            if (subProblem == -1) continue;
            // Choose the optimal solution from the subproblems and add one
            res = min(res, subProblem + 1);
        }
        // Store the calculation result in the memo
        memo[amount] = (res == INT_MAX) ? -1 : res;
        return memo[amount];
    }
};

class Solution:
    def __init__(self):
        self.memo = []
    
    def coinChange(self, coins: List[int], amount: int) -> int:
        self.memo = [-666] * (amount + 1)
        # Initialize the memo with a special value that
        # won't be picked, representing it has not been
        return self.dp(coins, amount)
    
    def dp(self, coins, amount):
        if amount == 0: return 0
        if amount < 0: return -1
        # Check the memo to prevent repeated calculations
        if self.memo[amount] != -666:
            return self.memo[amount]

        res = float('inf')
        for coin in coins:
            # Calculate the result of the subproblem
            subProblem = self.dp(coins, amount - coin) 

            # Skip if the subproblem has no solution
            if subProblem == -1: continue
            # Choose the optimal solution from the subproblems and add one
            res = min(res, subProblem + 1)
        # Store the calculation result in the memo
        self.memo[amount] = res if res != float('inf') else -1
        return self.memo[amount]

import "math"

func coinChange(coins []int, amount int) int {
    memo := make([]int, amount + 1)
    for i := range memo {
        memo[i] = -666
    }
    // Initialize the memo with a special value that won't
    // be taken, representing that it has not been
    return dp(coins, amount, memo)
}

func dp(coins []int, amount int, memo []int) int {
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }
    // Check the memo to prevent repeated calculations
    if memo[amount] != -666 {
        return memo[amount]
    }

    res := math.MaxInt32
    for _, coin := range coins {
        // Calculate the result of the subproblem
        subProblem := dp(coins, amount - coin, memo)

        // Skip if the subproblem has no solution
        if subProblem == -1 {
            continue
        }
        // Choose the optimal solution in the subproblem and then add one
        res = min(res, subProblem + 1)
    }
    // Store the calculation result in the memo
    if res == math.MaxInt32 {
        memo[amount] = -1
    } else {
        memo[amount] = res
    }
    return memo[amount]
}

var coinChange = function(coins, amount) {
    let memo = new Array(amount + 1).fill(-666);
    // Initialize the memo with a special value that
    // won't be picked, representing it has not been
    return dp(coins, amount, memo);
}

function dp(coins, amount, memo) {
    if (amount === 0) return 0;
    if (amount < 0) return -1;
    // Check the memo to prevent repeated calculations
    if (memo[amount] !== -666) {
        return memo[amount];
    }

    let res = Infinity;
    for (let coin of coins) {
        // Calculate the result of the subproblem
        let subProblem = dp(coins, amount - coin, memo);

        // Skip if the subproblem has no solution
        if (subProblem === -1) continue;
        // Choose the optimal solution from the subproblem and add one
        res = Math.min(res, subProblem + 1);
    }
    // Store the calculation result in the memo
    memo[amount] = res === Infinity ? -1 : res;
    return memo[amount];
}

Without drawing a diagram, it's evident that the "memoization" significantly reduces the number of subproblems, completely eliminating redundancy. Therefore, the total number of subproblems won't exceed the amount n, meaning the number of subproblems is $O(n)$. The time to process one subproblem remains constant at $O(k)$, making the total time complexity $O(kn)$.

Iterative Solution with the DP Array

Of course, we can also use the dp table in a bottom-up manner to eliminate overlapping subproblems. Regarding "state," "choice," and the base case, there is no difference from before. The definition of the dp array is similar to the dp function, where the "state," meaning the target amount, is used as a variable. However, in the dp function, it is reflected in the function parameters, while in the dp array, it is reflected in the array indices:

Definition of the dp array: When the target amount is i, at least dp[i] coins are needed to make up the amount.

Based on the dynamic programming framework provided at the beginning of our article, the following solution can be written:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // The array size is amount + 1, and the initial value is also amount + 1
        Arrays.fill(dp, amount + 1);

        // base case
        dp[0] = 0;
        // The outer for loop traverses all possible values of all states
        for (int i = 0; i < dp.length; i++) {
            // The inner for loop finds the minimum value among all choices
            for (int coin : coins) {
                // The subproblem has no solution, skip
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);

            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // the size of the array is amount + 1, and the initial value is also amount + 1
        vector<int> dp(amount + 1, amount + 1);

        dp[0] = 0;
        // base case
        // the outer for loop is traversing all possible values of all states
        for (int i = 0; i < dp.size(); i++) {
            // the inner for loop is finding the minimum value of all choices
            for (int coin : coins) {
                // the subproblem has no solution, skip
                if (i - coin < 0) {
                    continue;
                }
                dp[i] = min(dp[i], 1 + dp[i - coin]);

            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
};

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # The array size is amount + 1, and the initial value is also amount + 1
        dp = [amount + 1] * (amount + 1)

        dp[0] = 0
        # base case
        # The outer for loop is traversing all possible values of all states
        for i in range(len(dp)):
            # The inner for loop is finding the minimum value among all choices
            for coin in coins:
                # The subproblem has no solution, skip
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i], 1 + dp[i - coin]) 

        return -1 if dp[amount] == amount + 1 else dp[amount]

func coinChange(coins []int, amount int) int {
    // the array size is amount + 1, and the initial value is also amount + 1
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }

    // base case
    dp[0] = 0
    // the outer for loop is traversing all possible values of all states
    for i := 0; i < len(dp); i++ {
        // the inner for loop is finding the minimum value among all choices
        for _, coin := range coins {
            // the subproblem has no solution, skip
            if i - coin < 0 {
                continue
            }
            dp[i] = min(dp[i], 1 + dp[i - coin])

        }
    }
    if dp[amount] == amount+1 {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

var coinChange = function(coins, amount) {
    // The array size is amount + 1, and the initial value is also amount + 1
    let dp = new Array(amount + 1).fill(amount + 1);

    dp[0] = 0;
    // base case
    // The outer for loop is traversing all possible values of all states
    for (let i = 0; i < dp.length; i++) {
        // The inner for loop is finding the minimum value of all choices
        for (let coin of coins) {
            // The subproblem has no solution, skip
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);

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

3. Final Summary

The first problem about the Fibonacci sequence explained how to optimize the recursion tree using a "memoization" or "dp table" approach. It clarified that these two methods are essentially the same, just differing in top-down and bottom-up approaches.

The second problem about making change demonstrated how to systematically determine the "state transition equation." Once you write a brute-force recursive solution using the state transition equation, the rest is optimizing the recursion tree and eliminating overlapping subproblems.

If you are not very familiar with dynamic programming and have made it this far, you deserve applause. I believe you have already grasped this algorithm design technique.

There is no special technique for computers to solve problems; the only solution is exhaustive search, exploring all possibilities. Algorithm design is primarily about first thinking "how to exhaustively search" and then pursuing "how to search smartly."

Listing the state transition equation addresses the "how to exhaustively search" problem. It is considered difficult because many exhaustive searches require recursion, and some problem solutions have complex solution spaces that are not easy to fully enumerate.

Memoization and DP table are about pursuing "how to search smartly." The idea of trading space for time is a surefire way to reduce time complexity. Besides this, what else can be done?

We will have a chapter dedicated to explaining dynamic programming problems. If you have any questions, feel free to revisit this article. I hope readers will focus on "states" and "choices" when reading each problem and solution, to develop their understanding of this framework and use it proficiently.