preface
The previous blog summed up dynamic programming, but there were a lot of things I didn’t understand as a beginner, so I found a great explanation on the Internet, and it was really good. Let me reprint.
The original article is linked to resources below.
1. Detailed explanation of dynamic programming routine
The following is a detailed dynamic programming for the Fibonacci sequence and the small change problem. If you just want to see the answer to this question, go to the end.
Dynamic programming algorithms seem to be very esoteric algorithms. You will find them in the advanced techniques section of some interview or algorithm books, and the words such as state transition equations, overlapping subproblems, optimal substructures and so on May put you off.
And, when you look at the code that solves a problem with dynamic programming, and you think how clever it is to solve a problem, but it’s hard to understand, you might be surprised at how someone came up with this solution.
In fact, dynamic programming is a common “algorithmic design technique”, there is nothing esoteric, as for all kinds of lofty terms, that is used to scare people, as long as you experience a few, the meaning of these terms are obvious, and it is very simple.
The reason why the final solution looks so neat is that dynamic programming follows a fixed process: recursive violence -> recursive solution with a memo -> non-recursive dynamic programming. It’s a step-by-step process, and if you look at the final solution of non-recursive dynamic programming without the preparation you’ve already done, you’re going to be overwhelmed.
And, of course, if you’ve seen a lot, if you’ve thought about it a lot, you can write a non-recursive solution to dynamic programming in one step. Any skill needs to practice, we first follow this process to go, the algorithm design is also these routines, beyond that, really nothing advanced.
In the following, the three processes are described by demytifying dynamic programming with two relatively simple examples: Fibonacci and the penny problem. I will write several articles on how to use dynamic programming techniques to solve more complex classical problems.
First of all, the first example, which is almost dead, is the Fibonacci sequence. The simplicity of this example will allow you to focus on the general ideas and techniques behind the algorithm without getting bogged down in the obscure details. Later, there are difficult examples.
Step one, violent recursive algorithm
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
Copy the codeI don’t need to say much about this, but this is the example that teachers seem to use when they talk about recursion in school. We also know that writing code like this is simple and easy to understand, but it’s inefficient. What’s inefficient? So let’s say n is equal to 20, so let’s draw the recursion tree.
PS: Whenever you have a problem that requires recursion, it is a good idea to draw a recursion tree. This will help you to analyze the complexity of the algorithm and find out why the algorithm is inefficient.
What about this recursion tree? So to compute the original problem F (20), I have to compute the subproblems F (19) and f(18), and then to compute f(19), I have to compute the subproblems F (18) and f(17), and so on. Finally, when you get f(1) or f(2), and you know the result, you can just return the result, and the recursion tree doesn’t grow down anymore.
How to calculate the time complexity of recursion algorithm? Number of subproblems times how long it takes to solve a subproblem.
Number of subproblems, the total number of nodes in the recursion tree. Obviously, the total number of nodes in the binary tree is exponential, so the number of subproblems is O(2^n).
The time to solve a subproblem, in this algorithm, there is no loop, just f(n-1) + f(n-2) an addition operation, and the time is O(1).
So, the time complexity of this algorithm is O(2^n), exponential, explosion.
If you look at the recursion tree, it’s clear why the algorithm is inefficient: there’s a lot of double counting, like f(18) is counted twice, and as you can see, the recursion tree at the root of f(18) is huge, so it takes a lot of time to do it again. Moreover, it is not only f(18) that is double-counted, so this algorithm is extremely inefficient.
This is the first property of dynamic programming problems: overlapping subproblems. Now, let’s try to solve this problem.
Step 2. Recursive solution with memo
A clear problem is half solved. However, the reason for the time is the double calculation, so we can create a “memo”, each time you calculate the answer to a subproblem, do not return to the “memo” first and then return; Check the “memo” for each subproblem. If the problem has been solved before, use the answer instead of calculating it.
Usually you use an array for this “memo,” but you can also use a hash table (dictionary), the idea is the same.
int fib(int N) {
if (N < 1) return 0;
// The memo is fully initialized to 0
vector<int> memo(N + 1.0);
return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
if (n == 1 || n == 2) return 1;
if(memo[n] ! =0) return memo[n];
// Not counted
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
Copy the codeNow, draw the recursion tree, and you’ll see what the memo does.
In fact, the recursion algorithm with “memo” transforms a recursion tree with huge redundancy into a recursion graph with no redundancy by “pruning”, which greatly reduces the number of subproblems (i.e. nodes in the recursion graph).
What is the time complexity of the recursive algorithm? Number of subproblems times how long it takes to solve a subproblem.
The number of subproblems is the total number of nodes in the graph. Since there is no redundant calculation in this algorithm, 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 a subproblem, again, there’s no loop, is order one.
Therefore, the time complexity of this algorithm is O(n). Instead of brute force algorithms, it’s dimension reduction strikes.
At this point, recursive solutions with memos are as efficient as dynamic programming. In fact, it’s pretty much the same idea as dynamic programming, except it’s called top-down, and dynamic programming is called bottom-up.
What is “top down”? Notice that the recursion tree that we’ve just drawn is going from top to bottom, from a large original problem like F (20), breaking it down until f(1) and f(2) hit the bottom, and then returning the answer one level at a time. This is called “top to bottom.”
What does “bottom up” mean? Instead, we start at the bottom, at the simplest, at the smallest problem, f(1) and f(2), and we work our way up to the answer we want, f(20), and that’s the idea of dynamic programming, and that’s why dynamic programming is generally done by going out of recursion and doing it through iterations.
Step 3. Dynamic programming
Inspired by the previous step “memo”, we can separate this “memo” into a table, called DP Table, on this table to complete the “bottom up” calculation would not be beautiful!
int fib(int N) {
vector<int> dp(N + 1.0);
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[N];
}
Copy the code
It makes sense to draw a picture, and you see that this DP table is very much like the pruning table, only the other way around. In fact, the “memo” in the recursive solution with memo is the DP table after the final completion, so the two solutions are actually similar, and in most cases, the efficiency is basically the same.
Here, the term “dynamic transfer equation” is introduced, which is actually a mathematical form describing the structure of the problem:
Why is it called “state transition equation”? To sound high-end. You take f(n) and you want to make a state n, which is a transition from state n minus 1 and state N minus 2, and that’s called a transition, that’s all.
You will notice that all the 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 memo or DP table, revolve around different representations of this equation. This shows the importance of listing the “state transition equation”, which is the core of solving the problem. It’s easy to see that the state transition equation directly represents the violent solution.
Don’t look down on the violent solution, the hardest thing about dynamic programming is to write down the state transition equation, which is the violent solution. The optimization method is nothing more than a memo or DP table, there is no mystery at all.
At the end of this example, I’m going to do a detailed optimization. The careful reader will notice that, according to the Fibonacci state transition equation, the current state is only related to the previous two states. In fact, you do not need such a long DP table to store all the states, just find a way to store the previous two states. Therefore, further optimization can be made to reduce the space complexity to O(1) :
int fib(int n) {
if (n < 2) return n;
int prev = 0, curr = 1;
for (int i = 0; i < n - 1; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
Copy the codeOne may ask why another important feature of dynamic programming, optimal substructure, is not covered. This will be covered below. The Fibonacci example is not strictly a dynamic programming, but the purpose of this is to show how the design of the algorithm spirals. Nine times out of ten, dynamic programming comes into play when a problem requires an optimal solution or when you see loops and functions like Max and min in your code.
Change problem
Now, let’s look at the second example, the issue of pocket change, which will soon be solved with the details outlined above.
Topic: Here are k coins in denominations c1, C2… Ck, giving another sum n, asks what is the minimum number of coins you would need to make up the sum, and if that is not possible, say -1.
For example, if k = 3, the denomination is 1, 2, and 5, and the total amount is n = 11, then a minimum of 3 coins will be needed, which is 11 = 5 + 5 + 1. Here’s the process.
First, the most difficult step is to write down the state transition equation. This question is easier to write:
In fact, this equation uses the property of “optimal substructure” : the solution of the original problem consists of the optimal solution of the subproblem. That is, f(11) is transferred from the optimal solution of f(10), f(9), and f(6).
Remember, in order to conform to the “optimal substructure,” the subproblems must be independent of each other. What does it mean to be independent? You don’t want to see a mathematical proof, but LET me show you an intuitive example.
For example, your original problem is to take an examination of the highest total score, so your subproblem is to take an examination of the highest language, mathematics take an examination of the highest…… In order to get the most out of each course, you need to get the highest multiple choice score and the highest fill in the blank score for each course…… Of course, the end result is that you get full marks in every course, which is the highest overall score.
You get the right result: the highest total score is the total score. Because this process conforms to the optimal substructure, “each subject to the highest” these subproblems are independent of each other, do not interfere with each other.
But, if add a condition: your language achievement and mathematics achievement will restrict each other, this negates the other. In that case, obviously the highest score you can get on the test is not the total score, and that would give you the wrong result. Because the subproblems are not independent, the Chinese and math scores cannot be optimized at the same time, so the optimal substructure is destroyed. Follow my public account labuladong to see more exciting algorithm articles
Going back to the coin problem, it is clear that the subproblems are not dependent on each other, but are independent of each other. So this is the right state transition equation.
And then you don’t have to worry about it, you just write the brute force recursive algorithm.
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
int ans = INT_MAX;
for (int coin : coins) {
// The amount is not reachable
if (amount - coin < 0) continue;
int subProb = coinChange(coins, amount - coin);
// The subproblem has no solution
if (subProb == -1) continue;
ans = min(ans, subProb + 1);
}
return ans == INT_MAX ? -1 : ans;
}
Copy the codeDraw the recursion tree:
Time complexity analysis: the total number of subproblems x the time of each subproblem. The total number of subproblems is the number of nodes in the recursion tree, which is hard to see, is O(n^k), but it’s exponential. Each subproblem contains a for loop of complexity O(k). So the total time complexity is order k times n to the k, exponential.
Two, with a memorandum of recursive algorithm
int coinChange(vector<int>& coins, int amount) {
// The memo is initialized to -2
vector<int> memo(amount + 1.2 -);
return helper(coins, amount, memo);
}
int helper(vector<int>& coins, int amount, vector<int>& memo) {
if (amount == 0) return 0;
if(memo[amount] ! = -2) return memo[amount];
int ans = INT_MAX;
for (int coin : coins) {
// The amount is not reachable
if (amount - coin < 0) continue;
int subProb = helper(coins, amount - coin, memo);
// The subproblem has no solution
if (subProb == -1) continue;
ans = min(ans, subProb + 1);
}
// Record the answers for this round
memo[amount] = (ans == INT_MAX) ? -1 : ans;
return memo[amount];
}
Copy the codeWithout drawing, it is clear that “memorandum” greatly reduces the number of subproblems, completely eliminating the redundancy of subproblems, so that the total number of subproblems will not exceed the amount n, that is, the number of subproblems is O(n). The time to deal with a subproblem is still O(k), so the total time complexity is O(kn).
Third, dynamic programming
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins)
if (coin <= i)
dp[i] = min(dp[i], dp[i - coin] + 1);
}
return dp[amount] > amount ? -1 : dp[amount];
}
Copy the code
To conclude, if you’re not familiar with dynamic programming, and you’re still here, I applaud you, I believe you’ve mastered the design of this algorithm.
The only way a computer can solve a problem is to exhaust all the possibilities. Algorithmic design is all about thinking “how to exhaust” and then pursuing “how to exhaust intelligently”.
Listing the dynamic transfer equation is to solve the problem of “how to exhaust”. It is difficult because many of the exhaustions require recursive implementation, and because some problems have complex solution Spaces that are not easy to exhaustive.
The memo and DP Table are in pursuit of “how to exhaustively intelligently”. The idea of using space for time is the only way to reduce the complexity of time. In addition, what can be played?
2. General ideas of dynamic programming to solve game problems
But intelligence is intelligence after all, the real algorithm problem is certainly not opportunistic to be able to fix. Therefore, this paper will use the stone game to tell how to use dynamic programming algorithm to solve such problems as “assuming two people are smart enough, who will win at last”.
The sets of game problems are almost the same, which will be explained by examples below. The core idea is to use tuples to store the game results of two people respectively on the basis of TWO-DIMENSIONAL DP. After you have mastered this technique, when you are asked about two pirates dividing a gem and two pirates taking a coin, you can tell them: I am too lazy to think about it, so I will write an algorithm to calculate it for you.
Our “Stone Game” changed to be more general:
You and your friends have a row of piles of stones in front of them, described by an array of piles and piles[I] to show how many stones there are in the i-th pile. You take turns taking stones, one pile at a time, but only the left or right pile. After all the stones are taken, whoever has the most stones wins.
The number of stones in the pile can be any positive integer, and the total number of stones can be any positive integer, thus breaking the first hand’s win. For example, there are three piles of stones = [1, 100, 3] and whether the first hand holds one or three, the decisive 100 is given to the next hand, who wins.
Assuming you are both smart, devise an algorithm that returns the difference between the final score (total number of stones) of the first and the second. For example, in the example above, the first hand gets 4 points, the second hand gets 100 points, and your algorithm should return -96.
Now, by extension, this is a Hard dynamic programming problem. The hard part of the game problem is, two people have to take turns choosing, and they’re both smart, so how do you program this?
Or emphasize the routine many times, first clear dp array meaning, and then similar to the stock buying and selling series of problems, as long as you find the “state” and “choice”, everything will fall into place.
Define the meaning of the DP array
There are many ways to define the same problem, and different definitions will lead to different state transition equations, but as long as the logic is right, the answer will always be the same.
I recommend that you don’t get caught up in the seemingly awesome, short-code quirks. It’s better to stick with the best interpretable, most scalable design ideas. This paper gives a general design framework for game problems.
Before introducing the meaning of the DP array, let’s take a look at what the final DP array looks like:
For the purposes of this article, a tuple is considered a class that contains the first and second attributes, and these attributes are abbreviated to FIR and SEC to save space. For example, according to the data above, we say dp[1][3]. Fir = 10, dp[0][1]. SEC = 3.
To answer a few questions that readers may have:
So this is a two-dimensional DP table that stores tuples, so how do you programmatically represent them? Half of this DP table is not used at all, how to optimize? Very simple, do not tube, first to solve the problem of the train of thought to understand then talk about it is not late.
Here’s what dp array means:
Dp [I][J].Fir says the highest score that the first hand can get for the piles[I... J]. Dp [I][J].Sec said the highest score the rear hand could get for the piles of piles[I... J]. To give an example, suppose that piles = [3, 9, 1, 2] and indexes start at 0 DP [0][1]. Fir = 9 means that the first person facing piles of stones [3, 9] will end up with a 9. Dp [1][3]. SEC = 2 means: against the stones [9, 1, 2], the backhand can finally get 2 points.Copy the codeThe answer we are looking for is the difference between the final scores of the first hand and the last hand, which by definition is DP [0][n-1].fir-DP [0][n-1].secdp[0][n−1].fir− DP [0][n−1].sec, which is to face the whole piles, The difference between the first hand’s optimal score and the second hand’s optimal score.
Ii. State transition equation
Writing the state transition equation is as simple as finding all the “states” and the “choices” that each state can make, and then choosing the best.
According to the previous definition of the DP array, there are obviously three states: index I at the beginning, index J at the end, and the current turn of the person.
Dp [I][J][E][E] PILES and piles of piles are piles and piles of pilesCopy the codeFor each state of the problem, there are two choices: choose the leftmost pile of rocks, or choose the rightmost pile of rocks. We can exhaustive all states like this:
n = piles.length
for 0 <= i < n:
for j <= i < n:
for who in {fir, sec}:
dp[i][j][who] = max(left, right)
Copy the codeThe above pseudo code is a general framework for dynamic programming, and there are similar pseudo codes for stock series problems. The difficulty with this question is that the two people choose alternately, that is to say, the choice of the first hand has an effect on the second hand. How can this be expressed?
According to our definition of dp array, it is easy to solve this difficulty and write the state transition equation:
Dp [I] [j]. Journal of fir = Max (piles + dp [I + 1] [I] [j]. The SEC, piles [j] + dp [j - 1]. [I] SEC) dp [I] [j]. Journal of fir = Max (select the most on the left side of the rocks, and select the most the right side of the rocks) # explain: When I was in front of the piles[I... J] I had two choices: # Either I chose the far left pile of stones and faced the piles[I +1... J] # but then it was the other side's turn, so I became the backhand; # Either I select the piles of rocks on the far right and face them to the piles[I...j-1] # but then it's their turn and I become the backhand. If dp = dp[I][J]. SEC = DP [I +1][J]. Dp [I][J].sec = DP [I][J-1].PILES [I +1].piles [I +1].piles [I +1].piles [I +1].piles [I +1].piles # If the first hand chose the far right pile and I was left with piles[I...j-1] # It was my turn and I became the first hand.Copy the codeWe can also find the base case based on the definition of the DP array, which is the simplest case:
Dp [I] [j]. Journal of fir = piles dp [I] [I] [j]. The SEC = 0 where 0 < = I = = j < n # : 'I' and 'J' are equal meaning there is only piles of stones in front of them [I] # so apparently the first hand has got 'PILES [I] #' and there are no stones in the back hand giving a score of 0Copy the code
Dp [I][j] : dp[I][j-1] : dp[I][j]
So instead of simply traversing the DP array line by line, the algorithm must traverse the array diagonally:
To be honest, it’s easy to go through a two-dimensional array diagonally, and you don’t really know how to do it, but think about it. Okay? With such a clever state transition equation listed, it’s really embarrassing if you don’t know how to code it…
Three, code implementation
To implement fir and SEC tuples, you can use Python, which comes with tuples; Or use the C++ pair; Or a three-dimensional array dp[n][n][2], where the last dimension is a tuple; Or we can write our own Pair class:
class Pair {
int fir, sec;
Pair(int fir, int sec) {
this.fir = fir;
this.sec = sec; }}Copy the codeThen we can directly translate our state transition equation into code, and notice the technique of traversing the number group in an oblique way:
/* Return the difference between the score of the first hand and the second hand */
int stoneGame(int[] piles) {
int n = piles.length;
// Initialize the dp array
Pair[][] dp = new Pair[n][n];
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
dp[i][j] = new Pair(0.0);
// Insert base case
for (int i = 0; i < n; i++) {
dp[i][i].fir = piles[i];
dp[i][i].sec = 0;
}
// Go through the group diagonally
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = l + i - 1;
// The first hand chooses the leftmost or rightmost score
int left = piles[i] + dp[i+1][j].sec;
int right = piles[j] + dp[i][j-1].sec;
// Use the state transition equation
if (left > right) {
dp[i][j].fir = left;
dp[i][j].sec = dp[i+1][j].fir;
} else {
dp[i][j].fir = right;
dp[i][j].sec = dp[i][j-1].fir;
}
}
}
Pair res = dp[0][n-1];
return res.fir - res.sec;
}
Copy the codeDynamic programming solutions are completely unreadable without the guidance of the state transition equation, but with the previous detailed explanation, the reader should be able to understand the meaning of this large chunk of code.
Also, notice that the calculation of DP [I][j] depends only on the elements to the left and below, so there must be some room for optimization, to convert to one-dimensional DP, imagine squashing a two-dimensional plane, that is, projecting into one dimension. However, one-dimensional DP is more complex and interpretable, so you don’t have to waste time trying to understand it.
Fourth, the final conclusion
This paper presents a dynamic programming method for solving game problems. The premise of a game problem is usually played between two intelligent people. The usual way to describe a game is to describe a two-dimensional DP array with tuples representing the optimal decision of the two people.
The reason for this design is that the first hand becomes the second hand after making the choice, and the second hand becomes the first hand after the other has made the choice. This role shift allows us to reuse previous results, typically dynamic programming flags.
Those of you who have read this should be able to understand how algorithms solve game problems. Learning algorithms, we must pay attention to the template framework of the algorithm, rather than some ideas that look awesome, and do not expect to write an optimal solution. Don’t use too much space, don’t try to optimize too early, and don’t be afraid of multi-dimensional arrays. The DP array is for storing information to avoid double counting, so just use it until I’m satisfied.
3. Dynamic programming design method: inductive thinking
You know the formula of dynamic programming, you don’t know how to write the state transition equation, you don’t know how to do it. In this paper, the longest increasing subsequence is used to describe a general technique of designing dynamic programming: the idea of mathematical induction.
The Longest Increasing Subsequence (LIS) is a classic problem, and the solution of dynamic programming is easy to think of. The time complexity is O(N^2). We use this problem to explain how to write dynamic programming from the simple to the profound. What’s hard to think of is using binary search, in order NlogN time, and we use a simple card game to help us understand this clever solution.
Look at the title first, it’s easy to understand:
Note the difference between the nouns “subsequence” and “substring.” A substring must be continuous, while a subsequence is not. So let’s start by designing a dynamic programming algorithm to solve this problem step by step.
The core design idea of dynamic programming is mathematical induction.
I believe you are not unfamiliar with mathematical induction, learned in high school, and the idea is very simple. Let’s say we want to prove a mathematical result, so let’s assume that the result is true for k<nk<n, and then try to prove that the result is true for k=nk=n. And if we can prove that, then this is true for k equals anything.
Similarly, when we design a dynamic programming algorithm, don’t we need an array of DP? We can assume that dp[0…i-1]dp[0… I −1] has all been calculated, and ask ourselves: How can WE calculate DP [I] from these results?
Just take the problem of the longest increasing subsequence for example. What does the value of dp[I] represent?
Our definition is as follows: dp[I] is the length of the longest increasing subsequence ending in nums[I].
Here are two examples:
The evolution process of the algorithm is as follows:
According to this definition, our end result (the maximum length of the subsequence) should be the maximum in the DP array.
int res = 0;
for (int i = 0; i < dp.size(); i++) {
res = Math.max(res, dp[i]);
}
return res;
Copy the codeThe reader may ask, since the result of each DP [I] in this process is visible to the naked eye, how should we design the algorithmic logic to correctly calculate each DP [I]?
So this is the main thing about dynamic programming, and to think about how to do state transitions, you can use the idea of mathematical induction:
We already know all the results of dp[0…4]dp[0…4], how can we deduce dp[5]dp[5] from these known results?
According to the definition of dp array, now we want to find the value of dp[5], that is, we want to find the longest increasing subsequence ending in nums[5].
Nums [5] = 3, since it is increasing subsequence, as long as we find the front end those smaller than 3 subsequence, then the 3 received finally, you can become a new increasing subsequence, and this new subsequence length plus one.
Of course, it is possible to form many new subsequences, but we only need the longest one, taking the length of the oldest sequence as the value of DP [5].
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
Copy the codeThe logic of this code can be used to calculate DP [5]. So at this point, we’re almost done with the algorithm. The reader may ask, we just calculated dp[5], dp[4], DP [3] how to calculate these?
Like mathematical induction, you can already calculate DP [5], and everything else can be calculated:
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1); }}Copy the codeOne more detail is that the DP array should all be initialized to 1, since the subsequence must at least contain itself, so the length should be at least 1. Let’s look at the full code:
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// The dp array is all initialized to 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1); }}int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
Copy the codeSo now we have solved this problem, in order N^2 time. To summarize the design process of dynamic programming:
First, clarify the meaning of the data stored in the DP array. This is an important step, and if it is not done properly or clearly, it will hinder the next step.
Then, according to the definition of dp array, using the idea of mathematical induction, assuming that dp[0…i-1]dp[0… I −1] are known, try to find out dp[I]dp[I], once this step is completed, the whole problem is basically solved.
But if you can’t do this, it is likely that the definition of the DP array is not appropriate and you need to redefine the meaning of the DP array. Or it could be that the DP array does not store enough information to come up with the next answer, and that you need to expand the DP array into a two-dimensional or even three-dimensional array.
Finally, think about what the base case of the problem is, and then initialize the DP array to make sure the algorithm works correctly.
Summary & References
summary
This blog post is a reprint summary for a deeper understanding of dynamic programming. Thanks to the original author, here is the link.
The resources
- Detailed analysis of dynamic programming sets
- [LeetCode] A Coin Change
- [LeetCode]877. The game of stones
- General idea of dynamic programming to solve game problems
- Dynamic programming design methods: Inductive thinking
- [LeetCode]300. Longest ascending subsequence