“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”
preface
The current series related to “dynamic programming” includes: “dynamic programming – path problem” which has been completed and “dynamic programming – backpack problem” which is being updated.
This is the default you have a certain “dynamic programming” understanding of the series of articles.
But in fact, many students may be new to algorithms, still in the use of “naive/violent solutions” to solve algorithm problems stage, do not understand the “dynamic programming”.
So I’ve pulled out articles that I wrote about six or seven years ago (more as study notes at the time) to help you get a basic understanding of dynamic programming.
It should be noted that this paper only stays on the perceptual understanding of “dynamic programming”, and does not go deep into the essential relationship between dynamic programming and graph theory.
So it’s more for beginners to algorithms.
Here is the text.
The evolution process
Never understood the difference between “dynamic programming” and “memorized search.”
I always think that the difficulty of dynamic programming lies in the abstract definition of “state” and the derivation of “state transition equation”, and there is no specific law to follow.
However, from the perspective of gradual algorithm optimization, dynamic programming evolves more in the following ways:
❝
Violent recursion -> memorized search -> dynamic programming.
❞
It can even be said that almost all “dynamic programming” can be transformed by “violent recursion”, provided that the problem is a “no aftereffect” problem.
From the simple enumeration of “cases”, evolved to the enumeration of “sets”.
There was no aftereffect
The so-called “no aftereffect” means that once the state of a certain stage is determined, the subsequent decision-making process and the final result will not be affected by the previous states.
It can be simply understood that when a recursive function is written, the result is uniquely determined when the variable parameters are determined.
You may still have trouble understanding what the “no aftereffects” question is. Let’s take a more concrete example: LeetCode 62. Unique Paths: Given a matrix, how many Paths can you take from the top left corner to the bottom right corner (the robot can only move to the right or down).
This is a classic “dynamic programming” introductory problem, is also a classic “no aftereffect” problem.
Its “no aftereffect” is reflected in: when given a certain state (a specific matrix and a starting point, such as (1,2)), then the number of paths from this point to the lower right corner is completely determined.
It doesn’t matter how you get there, it doesn’t matter whether the robot goes through (0,2) to (1,2) or (1,2) to (1,2).
This is known as the “no aftereffect” problem.
When we try to solve a problem with “dynamic programming”, we should first focus on whether the problem is a “no aftereffect” problem.
1: violent recursion
Often we are faced with a problem that can be solved by “dynamic programming” even though we clearly know it is a “no aftereffects” problem. We still find it difficult to get started.
My advice at this point is to write a violent recursive version first.
Let’s use the example of LeetCode 62. Unique Paths:
class Solution {
public int uniquePaths(int m, int n) {
return recursive(m, n, 0.0);
}
private int recursive(int m, int n, int i, int j) {
if (i == m - 1 || j == n - 1) return 1;
return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1); }}Copy the codeWhen I don’t know how to use “dynamic programming” to solve, I will design a recursive function.
The function is passed in the matrix information and the robot’s current position, and returns how many paths there are in the matrix from where the robot is to the lower right corner.
With this recursive function, the problem is to find the number of paths from (0,0) to the lower right corner.
Next, implement this function:
-
The Base case of the recursive method is when the robot is in the last row or column of the matrix, so there is only one way to go.
-
The rest: The robot can go either right or down, so for a given position, the number of paths to the lower right is equal to the number of paths to the lower right from the position on its right + the number of paths to the lower right from the position below it. That is, recursive(m,n, I +1,j) + Recursive (m,n, I,j+1), both of which can be solved by recursive functions.
Actually, at this point, we’ve solved this problem.
But there is also a serious “performance” problem with this approach.
2: memorized search
If we submit our code to LeetCode, we get timeout.
The solution of “violent recursion” is “slow”.
We know that the essence of all recursive functions is “stack pressing” and “stack flipping.”
Since this process is slow, can we solve the timeout problem by changing the recursive version of the brute force solution to the non-recursive brute force solution?
The answer is no, because what causes timeout is not the cost of using recursion.
But in the calculation process, we did a lot of double counting.
Let’s try to expand the recursive process to see how many steps:
It’s not hard to see that there’s a lot of double counting going on during recursive expansion.
As we go through the recursion, the number of double-counts grows exponentially.
This is why the violent recursion solution is slow.
Timeout = timeout = timeout = timeout = timeout = timeout
class Solution {
private int[][] cache;
public int uniquePaths(int m, int n) {
cache = new int[m][n];
for (int i = 0; i < m; i++) {
int[] ints = new int[n];
Arrays.fill(ints, -1);
cache[i] = ints;
}
return recursive(m, n, 0.0);
}
private int recursive(int m, int n, int i, int j) {
if (i == m - 1 || j == n - 1) return 1;
if (cache[i][j] == -1) {
if (cache[i + 1][j] == -1) {
cache[i + 1][j] = recursive(m, n, i + 1, j);
}
if (cache[i][j + 1] = = -1) {
cache[i][j + 1] = recursive(m, n, i, j + 1);
}
cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
}
returncache[i][j]; }}Copy the codeThe practice of caching intermediate results in a violent recursion to ensure that the same case is only calculated once is called a memorized search.
After making these improvements, I submitted LeetCode to AC and got a good rating.
If we think about it a little bit more, we can see that the number of visits per case (per point) hasn’t changed during the entire process.
It just changed from “do it on every previous visit” to “do it only on the first visit.”
In fact, we can see by looking at the Recursive () method:
When we solve for a point, we depend on the sum.
So for every answer at one point, you need to access the results at two points.
This situation is caused by our top-down approach to solving the problem.
There is no intuitive way to determine when and how many times the results of which points will be accessed.
So we have to use an array of the same size as the matrix to “cache” all the intermediate results.
In other words, “memorized search” solves the problem of double counting, not the uncertainty of when and how many times the results will be accessed.
2.1: Suboptimal version of “memorized Search”
One last word on memorized search.
There are many blogs and materials on the Internet that write code like this when writing a “memorized search” solution:
class Solution {
private int[][] cache;
public int uniquePaths(int m, int n) {
cache = new int[m][n];
for (int i = 0; i < m; i++) {
int[] ints = new int[n];
Arrays.fill(ints, -1);
cache[i] = ints;
}
return recursive(m, n, 0.0);
}
private int recursive(int m, int n, int i, int j) {
if (i == m - 1 || j == n - 1) return 1;
if (cache[i][j] == -1) {
cache[i][j] = recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
}
returncache[i][j]; }}Copy the codeCompare this with the solution I provided above. If (cache[I][j] == -1);
In my solution, when calculating cache[I][j], I try to read cache[I +1][j] and cache[I][j+1] from “cache”, ensuring that each call to recursive() is required and not repeated.
Most solutions on the web only read the “cache” from the outer layer and call the recursive() subproblem without checking and calling the actual cache[I][J].
While both are significantly less computable (recursive() visits) than direct “violent recursion,” the latter is significantly more computable.
You might think it’s all “top down” anyway, so there’s no difference, right?
To do this, I provide the following experimental code to compare the number of calls to Recursive () :
class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
solution.uniquePaths(15.15);
}
private int[][] cache;
private long count; // Count the number of times a recursive function is called
public int uniquePaths(int m, int n) {
cache = new int[m][n];
for (int i = 0; i < m; i++) {
int[] ints = new int[n];
Arrays.fill(ints, -1);
cache[i] = ints;
}
// int result = recursive(m, n, 0, 0); // count = 80233199
// int result = cacheRecursive(m, n, 0, 0); // count = 393
int result = fullCacheRecursive(m, n, 0.0); // count = 224
System.out.println(count);
return result;
}
// Full cache
private int fullCacheRecursive(int m, int n, int i, int j) {
count++;
if (i == m - 1 || j == n - 1) return 1;
if (cache[i][j] == -1) {
if (cache[i + 1][j] == -1) {
cache[i + 1][j] = fullCacheRecursive(m, n, i + 1, j);
}
if (cache[i][j + 1] = = -1) {
cache[i][j + 1] = fullCacheRecursive(m, n, i, j + 1);
}
cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
}
return cache[i][j];
}
// Only the outer cache
private int cacheRecursive(int m, int n, int i, int j) {
count++;
if (i == m - 1 || j == n - 1) return 1;
if (cache[i][j] == -1) {
cache[i][j] = cacheRecursive(m, n, i + 1, j) + cacheRecursive(m, n, i, j + 1);
}
return cache[i][j];
}
// Do not use caching
private int recursive(int m, int n, int i, int j) {
count++;
if (i == m - 1 || j == n - 1) return 1;
return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1); }}Copy the codeThe purpose of using cache arrays is to reduce the number of recursive() calls.
We can minimize the number of calls to recursive() by making sure we check the cache array before each call to recursive().
This is a difference between and for a sample of 15, but it’s particularly important for some OJ where the card constant is particularly severe.
So I suggest you adopt the same strategy as I did for your “memorized search” solution:
Be sure to check the “cache” every time you access a recursive function. While this is a bit “unsappy,” it does the best job of memorizing search.
3: “top down” to “bottom up”
Why, you may wonder, do we need to improve “memorized searches” and specify when and how many times intermediate results are accessed?
Because once we can identify the access times and access times of the intermediate results, it gives us a huge improvement in our algorithm.
As mentioned earlier, we have to “cache” all the intermediate results because we cannot determine when and how many times the intermediate results will be accessed.
But if we can specify the access time and access times of intermediate results, at least we can greatly reduce the space complexity of the algorithm.
This involves a shift from “top down” to “bottom up.”
How to achieve the transition from “top down” to “bottom up” is understood through specific examples.
This is LeetCode 509. Fibonacci Number, the famous Fibonacci Number problem.
If you don’t know what a Fibonacci sequence is, check out wikipedia.
Since the Fibonacci formula is:
Naturally suitable for using recursion:
public class Solution {
private int[] cache;
public int fib(int n) {
cache = new int[n + 1];
return recursive(n);
}
private int recursive(int n) {
if (n <= 1) return n;
if (n == 2) return 1;
if (cache[n] == 0) {
if (cache[n - 1] = =0) {
cache[n - 1] = recursive(n - 1);
}
if (cache[n - 2] = =0) {
cache[n - 2] = recursive(n - 2);
}
cache[n] = cache[n - 1] + cache[n - 2];
}
returncache[n]; }}Copy the codeBut it still has the same problems we talked about before, which are caused by the fact that the direct recursion is top-down.
The space-time complexity of such a solution is: each value is computed once, using an array of length.
By looking at Fibonacci’s formula, we can see that in order to compute a solution, we only need to know the solution to the sum of the solutions.
And the solution of the sum is known.
So we can just start with the solution and iterate through it.
Since calculating the solution of a value depends only on the solution of the first digit and the solution of the first two digits of the value, we only need to cache the most recent intermediate results with a few variables:
class Solution {
public int fib(int n) {
if (n <= 1) return n;
if (n == 2) return 1;
int prev1 = 1, prev2 = 1;
int cur = prev1 + prev2;
for (int i = 3; i <= n; i++) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
returncur; }}Copy the codeIn this way, we reduce the original spatial complexity of the algorithm to: only using a few finite variables.
But not all dynamic programming is as simple as moving from top down to bottom up as Fibonacci.
It’s not a random thing to do, especially since we’ve written the solution to “violence recursion.”
Let’s go back to LeetCode 62.Unique Paths:
class Solution {
public int uniquePaths(int m, int n) {
// Because of our "violent recursion" function, the real variables are I and j (range: [0,m-1] and [0, n-1], respectively).
// Therefore, we recommend a two-dimensional DP array for storing results.
int[][] dp = new int[m][n];
// Base case in the "violent recursion" function
// We can directly find the last row and last column in dp (insert the last row and last column in the table)
for (int i = 0; i < n; i++) dp[m - 1][i] = 1
for (int i = 0; i < m; i++) dp[i][n - 1] = 1;
// Write a loop based on the logic (dependencies) used in the "brute recursion" function to handle other cases
// return the values of the last row and column in the table to the values of the other cells in the table
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
dp[i][j] = dp[i + 1][j] + dp[i][j + 1]; }}// Finally we want dp[0][0] (the upper left corner of the table, which is the starting point value)
return dp[0] [0];
// The original "violent recursion" call
// return recursive(m, n, 0, 0);
}
private int recursive(int m, int n, int i, int j) {
// base case
if (i == m - 1 || j == n - 1) return 1;
// The rest
return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1); }}Copy the codeIt is not hard to see that we can even write dynamic programming directly from violent recursion, without caring about the original problem.
Simple “dynamic programming” is actually a “tabulating” process:
First, the base case is used to determine the values of some positions in the table, and then the information of other cells is calculated based on the obtained values.
The dependencies used in the calculation are the “what else” processing logic in our “violent recursion”.
The nature of dynamic programming
The essence of dynamic programming is still enumeration: enumerating all the schemes and finding the best solution.
But unlike violent recursion, dynamic programming involves much less double counting.
Because the historical results that you rely on are saved, you save a lot of double counting.
In this respect, both “dynamic programming” and “memorized search” are similar.
To store historical results, it is necessary to use a data structure. In DP, we usually use one dimensional array or two dimensional data for storage, let’s say dp[].
So to solve the DP problem we have the following procedure
-
State definition: determine the meaning of the elements in dp[], i.e. what does DP [I] stand for
-
State transition: Determine the relationship between elements of DP [], dp[I] from which the lattice dp[I] is deduced. Dp [I] = dp[I – 1] + dp[I – 2]
-
Start value: base case, which cells in dp[] can be obtained directly. For example, in the Fibonacci sequence, dp[0] = 0 and DP [1] = 1
Eliminate “aftereffects”
We know that the premise of using “dynamic programming” is “no aftereffect” of the problem.
But sometimes the problem of “no aftereffect” is not easy to show.
We need to introduce one more dimension to “eliminate”.
For example, for the classic “stock problem” in LeetCode, when using dynamic programming to solve the problem, it is often necessary to introduce one more dimension to represent the state, and sometimes even to introduce another dimension to represent the number of purchases.
Note that the elimination is in quotes, but this is more of a “trick” that doesn’t really change the “aftereffect” of the problem, just makes it seem easier.
conclusion
At this point we can answer the simple question of what is the difference between dynamic programming and memorized search.
“Memorized search” is essentially “violent recursion” with “caching” function:
It can only solve the problem of double calculation, and can not determine the access time and access times of the intermediate results, the essence is a “top-down” solution;
“Dynamic programming” is a “bottom-up” solution:
The access time and access times can be specified, which brings great space to reduce the space complexity of the algorithm, we can decide which intermediate results to keep according to the dependency relationship, without the need to “cache” all the intermediate results.