Click here to read more about algorithmic interviewing
preface
Before learning dynamic programming systematically, I could not understand the difference between “dynamic programming” and “mnemonic search”.
I always feel that dynamic programming is simply difficult because of the abstract definition of “state” and the derivation of “state transition equation”, without specific rules to follow.
This article will help you understand dynamic programming once and for all.
The evolution process
Violent recursion -> mnemonic search -> dynamic programming
In fact, dynamic programming is also practiced in this way.
It can be said that almost all “dynamic programming” can be transformed by “violent recursion”, provided that the problem is a “no aftereffect” problem.
There was no aftereffect
The so-called “no aftereffect” means that once the status of a certain stage is determined, the subsequent decision-making process and final result will not be affected by the previous various 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 be confused about what “no aftereffect” is. Given a matrix of m x n Paths, how many Unique Paths will there be from the top left to the bottom right (the robot can only move to the right or down).
This is a classic “dynamic programming” introductory problem, but also a classic “no aftereffect” problem.
Its “no aftereffect” is reflected in that when given a certain state (a concrete matrix of m x n and a certain starting point, such as (1,2)), the number of paths from this point to the lower right corner is completely determined.
And it doesn’t matter how you get there, it doesn’t matter whether the robot goes through the point (0,2) to get there (1,2) or through the point (1,1) to get there (1,2).
This is known as the “no aftereffect” problem.
When we try to solve a problem using “dynamic programming”, we should first pay attention to whether the problem is a “no aftereffect” problem.
1: Violence recursion
Often we are faced with a problem that can be solved by “dynamic programming”, even though we clearly know it is a “no aftereffect” problem. We still find it hard to get started.
My advice at this point is to write a violent recursive version first.
Paths 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 solve using “dynamic programming”, I design a recursive function called Recursive ().
The function passes in the matrix information and the robot’s current position and returns the number of paths to the lower right corner from the robot’s position in the matrix.
With this recursive function in hand, the problem is simply solving recursive(m, n, 0,0) : solving the number of paths from (0,0) to the bottom right.
Next, implement this function:
-
Base case: Since it is clear that the robot can only go down or right, the Base case of the recursive method can be determined when it is already in the last row or column of the matrix, that is, there is only one way to go.
-
The rest: The robot can go both right and down, so for a given position, the number of paths to the bottom right is equal to the number of paths to the bottom right from its right position + the number of paths to the bottom right from its bottom position. That is, recursive(m, n, I + 1, j) + recursive(m, n, I, j + 1), both of which can be solved by recursive functions.
And actually, we’ve solved this problem by now.
But there is a serious performance problem with this approach.
2: memorized search
If we submit our code above to LeetCode, we get a timeout result.
So the solution to “violent recursion” is “slow”.
We know that the nature of all recursive functions is “stack” and “stack”.
Since this process is slow, can we solve the timeout problem by changing the recursive violent solution to the non-recursive violent solution?
The answer is no, because timeouts are not caused by the cost of using “recursive” methods.
But in the calculation process, we did a lot of double counting.
Let’s try to expand the recursion process to see what steps:
It is not difficult to find that there is a lot of double calculation in the recursive expansion process.
As we go through the recursive process, the number of repetitions increases exponentially.
This is why the “violent recursion” solution is “slow”.
Since the timeout is caused by repeated computation, we naturally come up with a solution of “caching” the calculation results:
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 during violent recursion to ensure that the same situation is evaluated only once is called memorized search.
After making such improvements, submitting LeetCode can be AC and get a good rating.
If we think about it a little bit, we’ll see that the number of calls per case (per point) doesn’t change.
It just changed from “solve on every previous access” to “only really solve on the first access”.
In fact, we can see this by looking at recursive() :
When we solve for a certain point (I, j), it really depends on (I, j + 1) and (I + 1, j).
So for every one of these points, you have to access the results of two points.
This is the result of our top-down approach.
We cannot intuitively determine when and how many times the results of which points will be accessed.
So we had 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, but does not solve the uncertainty of the timing and frequency of access to results.
2.1: Sub-optimal version of “memorized search”
One last word on mnemonic search.
There are a number of blogs and sources on the web that write memorized search solutions in code that looks something like this:
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 codeContrast this with the solution I provided above. If (cache[I][j] == -1);
In my solution, I will try to read cache[I + 1][j] and cache[I][j + 1] from “cache” when calculating cache[I][j], ensuring that each call recursive() is required and not repeated.
Most of the solutions on the web only read the “cache” from the outer layer, instead of checking and calling recursive() to compute the sub-problem when the cache[I][j] is actually computed.
Although both are significantly less computations (recursive() times) than direct “violent recursion”, the latter is significantly more computations.
You might think it’s all “top down” anyway, wouldn’t it?
To do this, I provide the following experimental code to compare the number of times they call 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 calls to recursive functions
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 cache
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 recursive() calls only by ensuring that the cache array is checked before each recursive() call.
In the sample of data 15, this is the difference between O(393N) and O(224n), but is especially important for some OJ where the card constant is particularly severe.
So I suggest you adopt the same strategy as I do for your memorized search solution:
Be sure to “cache” check every time you access a recursive function. Although this is a bit “unsightly”, it makes the most of mnemonic search.
3: From “top down” to “Bottom up”
You might be wondering, why do we need to improve “memorized search” and specify when and how often intermediate results are accessed?
Because once we can clarify the access timing and frequency of intermediate results, it will bring huge room for improvement to our algorithm.
As mentioned earlier, we had to “cache” all intermediate results because we could not determine when and how many times they would be accessed.
However, if we can specify the access time and times of intermediate results, at least we can greatly reduce the spatial complexity of the algorithm.
This involves a shift in thinking from “top down” to “bottom up”.
How to make the transition from “top down” to “bottom up” is again understood through concrete 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 Fibonacci’s formula is:
Natural for 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 earlier, all because direct recursion is “top down”.
Such a solution has a spatio-temporal complexity of O(n) : each value is evaluated once, using an array of length N + 1.
By looking at the Fibonacci formula, we can see that to compute some n, we only need to know the solution of n-1 and the solution of n-2.
At the same time, the solutions of n = 1 and n = 2 are known (base case).
So we can start at n = 3 and iterate to get the solution to n.
Since calculating a solution to a value depends only on the first two bits of the value and the first two bits of the value, we only need to cache the most recent intermediate result 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 codeThus we reduce the algorithm from O(N) to O(1) : only a finite number of variables are used.
But not all “dynamic programming” is as simple as Fibonacci sequences to make the transition from “top down” to “bottom up”.
Of course, it’s not random, especially since we’ve already written a solution to violent recursion.
Let’s go back to LeetCode 62. Unique Paths:
class Solution {
public int uniquePaths(int m, int n) {
// Due to our "violence recursion" function, the real variables are I and j (range [0,m-1] and [0, n-1] respectively).
// So we recommend a two-dimensional dp array to store the results (equivalent to building a table)
int[][] dp = new int[m][n];
// Based on the base case in the violence recursion function
// We can directly calculate the value of the last row and the last column in the table (insert the last row and the 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 loops based on the logic (dependencies) used in the violence recursion function to handle other cases
// Select the values of the other cells in the table from the last row and column.
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]; }}// dp[0][0] = dp[0]
return dp[0] [0];
// The original "violence 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 based on “violent recursion” without caring what the original problem is.
Simple “dynamic programming” is a “form” process:
Firstly, the values of some positions in the table are determined according to the base case, and then the information of other grids is calculated according to the positions of the obtained values.
The dependencies used in the calculation are the “rest” logic of our “violent recursion”.
The nature of dynamic programming
The essence of dynamic programming is still enumeration: enumerate all the alternatives and find the best solution.
But unlike violent recursion, dynamic programming requires much less double-counting.
Because these historical results are stored, a lot of double counting is saved.
In this respect, “dynamic programming” and “memorized search” are similar.
To store historical results, it is necessary to use data structures. In DP, we usually use one-dimensional arrays or two-dimensional data for storage, assuming dp[].
So we have the following procedure for solving the DP problem
State definition: determine the meaning of the elements in dp[], i.e., what does dp[I] stand forState transition: Determine the relation between dp[] elements, from which DP [I] the cell is inferred. Dp [I] = dp[I – 1] + dp[I – 2]The starting value: base case, dp[] which boxes can be derived directly. For example, the Fibonacci sequence has dp[0] = 0 and DP [1] = 1
Elimination of “aftereffects”
We know that the premise of using “dynamic programming” is that the problem has “no aftereffect”.
But sometimes the problem of “no aftereffect” is not easy to reflect.
We need to introduce an additional dimension to “eliminate”.
For example, when solving the classic “stock problem” in LeetCode using dynamic programming, 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 elimination is in quotes, but it’s more of a “trick” that doesn’t really change the “aftereffect” of the problem, just makes it look easy.
Since this article is already too long, I will not expand on the “stock issue” here.
Later, a special chapter will be used to explain “stock problems”, so as to solve all “stock problems” with the same idea. Please look forward to it.
conclusion
At this point we can answer the question of what is the difference between “dynamic programming” and “memorized search”.
Mnemonic search is essentially violent recursion with caching:
It can only solve the problem of repeated calculation, but can not determine the access time and access times of intermediate results, which is essentially a “top-down” solution.
“Dynamic programming” is a “bottom-up” solution:
The access timing and access times can be clearly defined, which brings huge space to reduce the spatial complexity of the algorithm. We can decide which intermediate results to keep according to the dependency relationship, instead of “caching” all intermediate results.
The last
If the article is helpful to you, but also want to systematically learn “algorithms and data structures”.
Welcome to follow me, “brush through LeetCode” series is being updated. I will try to explain each topic in ten minutes