动态规划解题套路框架
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 322. Coin Change | 🟠 |
| 509. Fibonacci Number | 🟢 |
Prerequisites
Before reading this article, you should learn:
Tip
本文有视频版：Detailed Explanation of Dynamic Programming Framework。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
This article is an advanced version of my popular public account post from years ago, Dynamic Programming Explained, which received over 200 appreciations. I've added more valuable content, aiming to make this a comprehensive guide for solving dynamic programming problems.
Dynamic Programming (DP) can be a headache for many readers, but it is also the most skillful and interesting type of problem. This book dedicates an entire chapter to this algorithm, highlighting its importance.
This article addresses several questions:
- What is Dynamic Programming?
- What are the techniques for solving DP problems?
- How can you learn Dynamic Programming?
As you solve more problems, you'll notice that algorithmic techniques follow a few common patterns. Our subsequent chapters on dynamic programming use the problem-solving framework from this article. If you understand it, you'll find things much easier. That's why this article is placed in the first chapter, hoping to serve as a guiding principle for solving DP problems. Let's dive into the details.
Firstly, the general form of a dynamic programming problem is to find the optimal value. Dynamic programming is an optimization method in operations research, widely used in computer science problems, such as finding the longest increasing subsequence or the minimum edit distance.
Since we're looking for the optimal value, what is the core issue? The core of solving dynamic programming is exhaustive enumeration. To find the optimal value, you need to enumerate all possible solutions and then select the best one.
Is dynamic programming just about exhaustive enumeration? The DP problems I've seen are quite challenging!
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(状态1, 状态2, ...):
for 选择 in 所有可能的选择:
# At this point, the state has changed due to the choice made
result = 求最值(result, dp(状态1, 状态2, ...))
return result
# Bottom-up iterative dynamic programming
# Initialize base case
dp[0][0][...] = base case
# Perform state transitions
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)Next, we'll explain the basic principles of dynamic programming through the Fibonacci sequence problem and the coin change problem. The former aims to help you understand what overlapping subproblems are (the Fibonacci sequence doesn't involve finding the maximum value, so strictly speaking, it's not a dynamic programming problem), while the latter focuses on how to derive the state transition equation.
I. Fibonacci Sequence
LeetCode problem #509 "Fibonacci Number" is an example of this. Readers, please don't dismiss this example as too simple. Only simple examples allow you to fully concentrate on the universal ideas and techniques behind the algorithm, without getting 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 looks like this:
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 doesn't need much explanation; it seems that school teachers often use this as an example when teaching recursion. We also know that while this code is concise and easy to understand, it is extremely inefficient. Where does the inefficiency lie? Assume ( n = 20 ); please draw the recursion tree:
提示
Whenever you encounter a problem that requires recursion, it's best to draw a recursion tree. This is immensely helpful for analyzing the complexity of the algorithm and identifying the reasons for its inefficiency.
How do you understand this recursion tree? It means that to calculate the original problem ( f(20) ), I need to first calculate the subproblems ( f(19) ) and ( f(18) ). Then, to calculate ( f(19) ), I need to first solve the subproblems ( f(18) ) and ( f(17) ), and so on. Finally, when I encounter ( f(1) ) or ( f(2) ), the results are known, and I can return the result directly, at which point the recursion tree stops growing.
How do you calculate the time complexity of a recursive algorithm? It's the number of subproblems multiplied by the time it takes to solve one subproblem.
First, calculate the number of subproblems, which is the total number of nodes in the recursion tree. Obviously, 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 one addition operation ( f(n - 1) + f(n - 2) ), which takes ( O(1) ) time.
Therefore, the time complexity of this algorithm is the product of these two, which is ( O(2^n) ), an exponential level, explosive.
Observing the recursion tree, it's clear to see the reason for the algorithm's inefficiency: there is a lot of redundant computation. For example, ( f(18) ) is calculated twice, and you can see that the recursion tree rooted at ( f(18) ) is massive. Calculating it once more consumes a huge amount of time. Moreover, it's not just ( f(18) ) that is recalculated, so this algorithm is extremely inefficient.
This is the first property of dynamic programming problems: overlapping subproblems. Next, let's figure out how to solve this problem.
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, let's draw the recursion tree to understand what the "memoization" actually does.
In fact, the recursive algorithm with "memoization" transforms a recursion tree with massive redundancy into a recursion graph without any redundancy by "pruning," significantly reducing 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 it takes to solve one subproblem.
The number of subproblems is the total number of nodes in the graph. Since this algorithm has no redundant calculations, the subproblems are f(1), f(2), f(3) ... f(20). The number is proportional to the input size n = 20, so the number of subproblems is O(n).
The time to solve one subproblem, as mentioned earlier, involves no loops and is O(1).
Therefore, the time complexity of this algorithm is O(n), which is a significant improvement over the brute-force approach.
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 picture makes it easy to understand. You'll notice that this DP table is very similar to the result after "pruning" in the previous example, just calculated in reverse:
In fact, the "memo" array in the recursive solution with memoization is essentially the same as the dp array in this solution once it's completed. Comparing the execution processes of the two algorithms on the visualization panel can help you see their connection more intuitively.
So, top-down and bottom-up approaches are fundamentally quite similar, and in most cases, their efficiency is also roughly the same.
Further Exploration
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"? It just sounds sophisticated.
The function parameter f(n) changes continuously, so you can think of the parameter n as a state. This state n is derived from the transition (addition) of states n - 1 and n - 2. This is what we call state transition, nothing more.
You'll notice that all operations in the above solutions, such as return f(n - 1) + f(n - 2), dp[i] = dp[i - 1] + dp[i - 2], and the initialization of the memoization or DP table, revolve around different representations of this equation.
The importance of formulating the "State Transition Equation" is evident. It is the core of solving the problem, and it is easy to see that the state transition equation directly represents the brute-force solution.
Never underestimate brute-force solutions. The most challenging part of dynamic programming problems is writing this brute-force solution, i.e., the state transition equation.
Once you have the brute-force solution, optimization methods are simply using memoization or a DP table, with no further mysteries.
To wrap up this example, let's discuss a detail optimization.
Careful readers will notice that, according to the Fibonacci sequence's state transition equation, the current state n only depends on the previous two states n-1 and n-2. Therefore, you don't need a long DP table to store all states; you only need to store the previous two states.
So, you can further optimize to reduce the space complexity to O(1). This is 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_1func 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.
提示
Regarding the issue of optimal substructure, the following article Dynamic Programming Q&A will further discuss with examples.
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 -1func 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;
}相关信息
Here, the signatures of the coinChange and dp functions are identical, so theoretically, there's no need to write an additional dp function. However, for the sake of clarity in the following explanations, we'll still write a separate dp function to handle the main logic.
Also, I often see readers asking why we add 1 to the result of subproblems (subProblem + 1) instead of adding the coin value or something else. Let me clarify this once and for all: the key to dynamic programming problems lies in the definition of the dp function/array. What does the return value of your function represent? Once you understand this, you'll know why we add 1 to the return value of subproblems.
At this point, the state transition equation is essentially complete. The algorithm described above is already a brute-force solution, and its mathematical form represents the state transition equation:
So, the problem is essentially solved at this point. However, we need to eliminate overlapping subproblems. For example, consider amount = 11, coins = {1,2,5} and draw a recursion tree to see:
Time Complexity Analysis of Recursive Algorithm: Total number of subproblems x Time to solve each subproblem.
The total number of subproblems is the number of nodes in the recursion tree. However, the algorithm performs pruning, and the timing of pruning depends on the specific coin denominations given in the problem. Therefore, it's difficult to precisely calculate the number of nodes in the tree. In such cases, we typically estimate an upper bound for the time complexity based on the worst-case scenario.
Assume the target amount is n and the number of given coins is k. In the worst case, the height of the recursion tree is n (using only coins of denomination 1), and if we assume it's a full k-ary tree, the total number of nodes is on the order of k^n.
Next, consider the complexity of each subproblem. Since each recursive call includes a for loop, the complexity is O(k). Multiplying these together gives a total time complexity of O(k^n), which is exponential.
Recursive with Memoization
Similar to the Fibonacci sequence example, we can eliminate overlapping subproblems by using memoization with just a slight modification:
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 calculated
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 calculated
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 calculated
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 calculated
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 calculated
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];
}Let's not draw a picture. It's obvious that the "memoization" significantly reduces the number of subproblems, completely eliminating redundancy in subproblems. Therefore, the total number of subproblems will not exceed the amount n, meaning the number of subproblems is O(n). The time to handle one subproblem remains the same, which is O(k), so the overall time complexity is O(kn).
Iterative Solution Using dp Array
Of course, we can also use a dp table from bottom to top to eliminate overlapping subproblems. The concepts of "state," "choices," and the base case remain the same as before. The definition of the dp array is similar to the dp function we discussed earlier, where the "state," or target amount, is used as a variable. However, the dp function is represented by function parameters, while the dp array is represented by 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 code framework provided at the beginning of our article, we can write the following solution:
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];
};相关信息
Why are the values in the dp array initialized to amount + 1? This is because the maximum number of coins needed to make up the amount can only be equal to amount itself (using only 1-unit coins). Initializing to amount + 1 is equivalent to initializing to infinity, which facilitates finding the minimum value later. Why not initialize directly to the maximum integer value Integer.MAX_VALUE? Because later we have dp[i - coin] + 1, which could lead to integer overflow.
Summary
The first Fibonacci sequence problem explains how to optimize the recursive tree using a "memoization" or "dp table" approach. It clarifies that these two methods are essentially the same, differing only in their top-down or bottom-up approaches.
The second coin change problem demonstrates how to systematically determine the "state transition equation." Once you write the brute-force recursive solution using this equation, the rest is just optimizing the recursive tree to eliminate overlapping subproblems.
If you're not familiar with dynamic programming and have made it this far, you deserve a round of applause. I believe you've mastered the design techniques of this algorithm.
Computers solve problems without any special tricks; their only method is exhaustive search, exploring all possibilities. Algorithm design is about first thinking "how to exhaustively search" and then striving for "how to search smartly."
Listing the state transition equation addresses the "how to exhaustively search" part. It's considered difficult because many exhaustive searches require recursion, and some problems have complex solution spaces that are not easy to fully enumerate.
Memoization and DP tables aim to achieve "smart exhaustive search." The idea of trading space for time is the key to reducing time complexity. Besides this, what other tricks are there?
We will have a dedicated chapter on dynamic programming problems later. If you have any questions, feel free to revisit this article. I hope readers will focus on the concepts of "state" and "choice" when reading each problem and solution, to develop their own understanding and apply the framework confidently.
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
