All you want to know about dynamic planning is here!

2020-12-08 14:29:18

Produce | AI Technology base

What is dynamic programming ？ What's important about it ？

In this paper , I will introduce you to Richard Bellman stay 20 century 50 Dynamic programming proposed in the s （dynamic programming） Concept , It's a powerful algorithmic design technique —— Break the problem down into small problems , Store their solutions , By combining them together , Finally, we get the solution to the original problem .

FAANG The most difficult questions in programming interviews usually fall into this category . You may also be asked to solve such problems during the interview , therefore , The importance of understanding this technology is self-evident . Next , I'll explain what dynamic planning is , Give a secret to solve dynamic programming problem , And I'd like to share with you a few examples , So that you can better understand its application situation and application method .

Just like my previous articles on programming interviews , In this paper , I'm going to share my thinking process when I use this method to solve problems , So when you're faced with one of these problems , According to this process, we can solve . There is no need to memorize , We just need to understand technology and practice , Turn ideas into code skills . The point of programming is not to learn a programming language , It's about analyzing the problem , Consider different solutions , Choose the best solution from it , And then it's translated into reality through some programming language .

Dynamic programming

Dynamic programming is a solution to optimization 、 General techniques for search and count problems , These problems can be decomposed into multiple subproblems . To apply dynamic programming , The problem must have the following two attributes ：

• Optimal substructure （Optimal substructure）
• Overlapping subproblems （Overlapping subproblems）

（1） Optimal substructure

If the size is n The optimal solution of the problem can be smaller than n The optimal solution of the same instance of the problem is derived , Then the problem has an optimal substructure .

for example , If the shortest route from Paris to Moscow goes through Berlin , So it can be made up of the shortest path from Paris to Berlin and the shortest path from Berlin to Moscow .

If a problem can be solved by combining the optimal solutions of non overlapping subproblems , This strategy is called divide and conquer . This is why merge sort and quick sort are not dynamic programming problems .

（2） Overlapping subproblems

Take a familiar example , Fibonacci sequence , That is, from the third item , Each of these terms is equal to the sum of the first two terms . The Fibonacci sequence can be expressed as

F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2)

We all say that a picture is worth a thousand words , therefore ......（ Excerpt from 《Elements of programming interviews》）

To work out F（n）, You need to work out F（n-1） and F（n-2）, however F（n-1） Again F（n-2） and F（n-3）. thus ,F（n-2） It's repetitive , Two different examples from the same problem —— Calculate a Fibonacci number .

This can be represented by a recursive function ：

• To solve a problem with a size of n The problem of , We can call the same function to solve an instance of the same problem , But the scale of the instance is smaller than that of the original problem .
• We call this function all the time , Until you reach the base use case , That is, the stop condition , Here is n = 0 or n = 1.

This leads to the relationship between recursion and dynamic programming .

Recursion and dynamic programming

conceptually , Dynamic programming involves recursion . We hope to solve the original problem through a small instance of the same problem , And recursion is the best way to do this in code . It differs from pure recursive functions in that , We're going to trade space for time ： We will store the optimal solution of each subproblem , Then the optimal solution of the original problem can be found efficiently .

Of course , This is not to say that we all have to use recursion to solve dynamic programming problems . You can also write dynamic planning solutions in an iterative way .

Bottom up dynamic planning

We need to fill in the table with solutions to all subproblems （ Start with the basic use case ）, And use it to build the solution we're looking for . This process is done iteratively , You can choose from one of the following categories as a data structure for storing solutions to subproblems ：

• Multidimensional （ And one dimension ） Array —— The most common method ;
• Hashtable ;
• Binary search tree ;

Top down dynamic planning

Write a recursive algorithm and add a cache layer , To avoid repeated function calls .

Maybe it looks a little confused now , But when it comes to examples later , Everything will be much clearer .

How to solve the dynamic planning problem

If a problem is to be solved by dynamic programming , We must have the properties of optimal substructure and overlapping subproblem . When intuition tells you that dynamic planning may be a viable solution , You need to verify that it has these two properties .

Now let's try to feel , What kind of problems can be solved by dynamic programming . All with “ find ” The first question ：

• ... ... Before n Elements ;
• ... ... All the way ;
• How many kinds? ... ... The way ;
• The first n individual ... ... ;
• ... ... The best solution for ;
• ... ... The shortest of / Maximum / Shortest path ;

It's all potential “ The candidate ”.

Steps to solve dynamic programming problems

Unfortunately , There is no general secret to solving dynamic programming problems . We need to go through a lot of problems , In order to gradually master the knack . It's really not easy , After all, it's probably the most difficult question you'll ever have in an interview . But don't be discouraged , simply , It's using relatively simple tools to model problems , There's no need for fancy data structures or algorithms .

I've solved a lot of these problems , But sometimes I still feel confused , No solution can be found . The more you practice , The easier it is. . Here are some of the tips for solving dynamic programming problems ：

• The overlapping subproblem and the properties of suboptimal structure are proved .
• Define subproblems .
• Define recursion .
• Write top-down or bottom-up dynamic planning solutions .

Complexity analysis varies from problem to problem , But generally speaking , Time complexity can be expressed as ：

Time ~ Number of sub questions * Time of each sub question

Calculating the spatial complexity of a bottom-up solution is simple , Because it's equal to the space needed to store solutions to subproblems （ Multidimensional arrays ）.

Example

I've categorized the problems according to the number of independent dimensions involved . This step is not necessary , But I found that when designing solutions , It's very useful to follow certain mental models . As you write more and more code , You'll find patterns , And this is one of them . Try it , Use it if you find it useful .

One dimensional problem

（1） Fibonacci

Because now everyone is very familiar with this problem , So I'm going to give you a recursive solution ：

int fib(int n) {
if (n == 0 || n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
}

The process from recursion to top-down usually has a fixed pattern ：

• Check that the value we need is already in the cache . If it is , Just go back to it .
• If not , Caching solutions just before returning .
int fib(int n) {
vector<int> cache(n + 1, -1);
return fib_helper(n, cache);
}
int fib_helper(int n, vector<int> &cache) {
if(-1 != cache[n])
return cache[n];
if (n == 0 || n == 1)
cache[n] = 1;
else
cache[n] = fib_helper(n - 1, cache) + fib_helper(n - 2, cache);
return cache[n];
}

here , Use bottom-up solutions , We build a table （ Start with the basic use case ）, To form a solution to the problem you're looking for . This table is a one-dimensional array ： We just need to store solutions to smaller problems , We can deduce the solution of the original problem .

int fib(int n) {
vector<int> f(n + 1, 0);
f = 1;
for(int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}

Extra space optimization

This method can further optimize memory , But it doesn't optimize time （ It's also possible to use other techniques to calculate the number sequence faster , But that's what another article is about ）, Just use 3 A variable , Instead of using arrays , Because we just need to track two values , namely f （n - 1） and f （n - 2）, We can get the output we want ——f （n）.

int fib(int n) {
if (n == 0 || n == 1)
return 1;
//Variables that represent f(n - 1), f(n - 2) and f(n)
int n1= 1, n2 = 1, f = 0;
for (int i = 2; i <= n; i++) {
f= n1 + n2;
n2 = n1;
n1 = f;
}
return f;
}

This method is more advanced , And more often . If you just need to track ：

• Several variables , Maybe we can get rid of one-dimensional arrays , Turn it into several variables .
• Several lines in two dimensional matrix , Maybe we can reduce it to a few one-dimensional arrays .
• wait ... ...

By reducing dimensions , We've increased the complexity of space . Now? , You don't have to remember all the details , But after some practice , Try to come up with these optimizations yourself , To enhance their ability to analyze problems and translate ideas into code . In the interview , I'll choose a simpler version , Only discuss potential optimizations . Only after writing your own “ Standardization ” Dynamic planning solutions , And when there's plenty of time , To implement these optimizations .

（2） climb stairs

Suppose you're climbing a little bit and there's n A staircase of steps , Every time I can climb 1 or 2 A stair . So if you want to climb to the top , How many different ways are there ？

example 1:

• Input ：2
• Output ：2
• explain ： There are two ways to get to the top ：1 rank +1 Step sum 2 rank

example 2:

• Input ：3
• Output ：3
• explain ： There are three ways to get to the top ：1 rank + 1 rank + 1 rank ,1 rank + 2 rank ,2 rank + 1 rank

Solution

Try to solve the problem yourself first . You might think of a recursive solution . Review my explanation and previous examples , See if you can write your own top-down solutions .

Hint ： Since the question is to “ How many ways ” start , Then you should be able to think of the potential for dynamic programming .

under these circumstances , If you want to reach number N rank , It's about to go through the N-1 Step or step N-2 rank , Because you can climb at one time 1 Step or 2 rank . If we can solve these two sub problems , We can find the solution to the general problem . We will f（N） It's called "to the first" N Number of methods of order .

• In order to get f（N）, We have to find out f（N-1） and f（N-2）.
• In order to get f（N-1）, We have to find out f（N-2） and f（N-3）.
• In order to get f（N-2）, We have to find out f（N-3） and f（N-4）.

There's no need to keep listing it , You should have found out ：

• This problem has overlapping subproblems ： You need to calculate many times f（N-2）, f（N-3）, f（N-4）,... ...
• This problem shows us the optimal substructure ： adopt f（N-1） and f（N-2） The best solution , You can get f（N） The best solution .

This means that we can solve the problem by dynamic programming .

Because I've already written the code in the last example , So there's no more code here .

You can try to write and test your solution in the link below .

（3） The longest increasing subsequence

Given an array of unsorted integers , Find the length of the longest increasing subsequence .

for example , For arrays [10,9,2,5,3,7,101,18] for , The output of 4, Sequence [2,3,7,101]

Solution

We need to find a size of n The length of the longest increment subsequence of the array of . It sounds like an optimization problem that can be solved by dynamic programming , So let's try . Suppose we already have a size of N The solution to the problem of , Call it s（n）, Then we add an extra element to the array , be called Y. that , You can reuse X To solve this new problem ？ This question usually brings us some inspiration .

ad locum , We need to know if the new element can extend any existing sequence ：

• Iterate over every element in the array , We call it X.
• If new elements Y Greater than X, Then a sequence can extend an element .
• If we have stored the solutions to all the subproblems , So getting the new length is very simple —— Just look it up in the array . We can get the solution of the new problem according to the optimal solution of the subproblem .
• Returns the length of the new longest increasing subsequence .

We seem to have some kind of algorithm . Continue with our analysis ：

• Optimal substructure ： We have proved that the size is n The optimal solution of the problem can be calculated from the optimal solution of the subproblem .
• Overlapping subproblems ： To calculate s（n）, You need to s（0）, s（1）,... ...,s（n-1）. Again , To calculate s（n-1）, You need to s（0）, s（1）,... ...,s（n-2）. The same problem requires multiple calculations .

Here's the code for the bottom-up solution .

int lengthOfLIS(const vector<int>& nums) {
if(nums.empty())
return 0;
vector<int> dp(nums.size(), 1);
int maxSol = 1;
for(int i = 0; i < nums.size(); ++i){
for(int j = 0; j < i; ++j){
if(nums[i] > nums[j]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxSol = max(maxSol, dp[i]);
}
return maxSol;
}

You can try to write and test your solution in the link below .

（4） How many? BST

For a given n, How many unique values are stored for 1... ...n Of BST（ Binary search tree ）？

Example ：

• Input ：5
• Output ：42
• explain ： Given n = 5, All in all 42 The only one BST

Solution

Let's take a look at this example . Suppose we have numbers 1、2、3、4、5, How to define BST？

I just need to choose one of them as the root , Let's assume it's a number 3, be ：

• 3 It's a root
• 3 On the left is the number 1 and 2
• 3 On the right is the number 4 and 5

We can solve （1,2） and （4,5） The same subproblem of （ Call it a solution for the time being L and R）, Count to 3 How many roots can form BST, namely L*R. If we do this for every possible root , And if you add up all the results , We can get the solution we need C（n）. As you can see , Start methodically with a few examples , It can help us design algorithms better .

Actually , We just need ：

• Choose an element as BST The root of the ;
• solve （1 To the root -1） and （ root +1 To n） The same problem with two numbers ;
• Multiply the two results of each subproblem ;
• Add it to our running total ;
• Go on to the next root ;

actually , We don't care what the numbers on either side of the array are . We just need the size of the subtree , The number of elements on the left and right sides of the root . Every instance of this problem produces the same result . In the previous example ,L and R All are C（2） Solution . We only need to calculate once C（2）, cache , And then reuse it .

int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp = 1;
dp = 1;
for(int i = 2; i <= n; ++i){
for(int j = 0; j < i; ++j){
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp.back();
}

You can try to write and test your solution in the link below .

Two dimensional problem

These problems are usually difficult to model , Because it involves two dimensions . A common example is , Iterate between two strings , Or move the map .

• The top-down solution is not much different than before ： Find recursion and use cache .
• For bottom-up solutions , One 2D An array is enough to hold the result . As I mentioned earlier , One or more one-dimensional arrays may be reduced , But there's no need to care too much about . This is mentioned just in case you are a little confused when you solve the problem .

I said in another article , Learning is iterative . First , Focus on understanding the basics , And then a little bit more detail .

（1） Minimum path sum

Given m×n Non negative grid of , Find a path from top left to bottom right , Minimize the sum of all numbers on the path .

Be careful ： You can only choose to move down or to the right .

Example ：

• Input ：[ [1,3,1], [1,5,1], [4,2,1] ]
• Output ：7
• explain ： Because the path 1→3→1→1→1 The sum is the smallest

Solution

Minimization should make you think of dynamic programming . Further analysis , The path can go through any cell C（i,j）（ It's not in the top or left border ）, Cell A = （i-1, j） and B=（i,j-1）. thus , We found that , Some problems need to be calculated many times . Besides , If we knew A and B The best solution , We can calculate the optimal solution of the current cell as min(sol (A),sol(B)) + 1, Because we can only use the current cell to express A or B, To move to the current cell, you need to take one more step . let me put it another way , This is an optimal substructure and overlap problem . We can use dynamic programming .

Here's the bottom-up solution .

int minPathSum(const vector<vector<int>>& grid) {
const int nrow = grid.size();
if(nrow == 0)
return 0;
const int ncol = grid.size();
vector<vector<int>> minSum(nrow, vector<int>(ncol, 0));
minSum = grid;
for(int col = 1; col < ncol; ++col)
minSum[col] = minSum[col - 1] + grid[col];
for(int row = 1; row < nrow; ++row)
minSum[row] = minSum[row - 1] + grid[row];
for(int col = 1; col < ncol; ++col){
for(int row = 1; row < nrow; ++row){
minSum[row][col] = min(minSum[row - 1][col], minSum[row][col - 1]) + grid[row][col];
}
}
return minSum[nrow - 1][ncol - 1];
}

Boundary conditions are defined on the boundary of a matrix . There is only one way to get points on the boundary ： Move one grid to the right or down from the previous point .

You can try to write and test your solution in the link below .

（2） knapsack problem

Given two arrays of integers val[0..n - 1] and wt [0 . .n-1], To express and respectively n Values and weights associated with items . meanwhile , Given an integer representing the capacity of the backpack W, seek val [ ] The maximum subset of , Ensure that the sum of the weights of this subset is less than or equal to W. The contents of the backpack must be kept intact , Or choose the complete item , Or don't choose （0 - 1 attribute ）.

Solution

Try to come up with a recursive solution . On this basis , Add a cache layer , We'll get a top-down dynamic planning solution ！

intend , For every object , We all have two choices ：

• We can put things like this in our backpacks （ If appropriate ), The total value of the backpack increases , Capacity reduction .
• We can give it up , The value and capacity in the backpack remain the same .

After trying all the combinations , We only choose the maximum value . The process is extremely slow , But it's the first step towards a final solution .

We have to decide between the two options （ Add an element to the collection or skip it ）, This choice is faced in many problems , So we have to understand , And understand where and how it's used .

// Recursive. Try to turn this into a piece of top-down DP code.int knapSack(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(val[n - 1] + knapSack(W - wt[n - 1],  wt, val, n - 1), knapSack(W, wt, val, n - 1));
}

Here's the bottom-up solution ：

// C style, in case you are not familiar with C++ vectorsint knapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max( val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}

（3） Longest common subsequence

Given two strings text 1 and text 2, Returns the length of their longest common subsequence .

A subsequence of a string is one that does not change the relative order of the rest of the characters , Delete some characters from the original string （ It can also be done without deleting ） New string generated after , for example ,“ace” yes “abcde” The subsequence , but “aec” No . The common subsequence of two strings is called its common subsequence .

Example ：

• Input ：text 1 = “abcde”, text 2 = “ace”
• Output ：3
• explain ： The longest common subsequence is “ace” , And its length is 3

Solution

Again , The calculation is the longest X The problem of , Dynamic planning should help .

Now that you have some experience with dynamic planning , I'll start with two properties in the example . We call a string A and B, The solution to this problem is f（A, B）, The idea is to see whether the last two characters are equal ：

• If equal , that LCS At least the length of 1. We need to call f(A[0:n-1], B[0:n-1]) To find the... Before the index LCS, And add 1, because A[n] and B[n] It's the same .
• If it's not equal , We just delete the last character of two strings —— Delete one at a time , And find the generated LCS The path of . let me put it another way , We take f(A[0: n-1], B) and f(A, B[0:n-1]) The maximum of .
• Overlapping subproblems ： Let's look at the possible calls ：(“abcde”, “ace”) produce x1 = (“abcd”, “ace”) and y1 = (“abcde”, “ac”);x1 Will produce x12 = (“abc”, “ace”) and y12= (“abcd”, “ac”);y1 Will produce (“abcd”, “ac”) and (“abcde”, “a”). As you can see , The same problem needs to be calculated many times .
• Optimal substructure ： It's very similar to the longest increaser sequence . If we're in one of these strings A’ Add an extra character to the , You can quickly calculate the solution from all the cached results , And these are the results of our understanding of A and B Got .

Although using examples to prove theory is not a good way to start a mathematical proof , But it's more than enough for programming interviews .

int longestCommonSubsequence(const string &text1, const string &text2) {
const int n = text1.length();
const int m = text2.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1,0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(text1[i-1] == text2[j-1])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}

You can try to write and test your solution in the link below .

summary

We have to understand these problems , Because many other problems are just variations on this basis , But don't memorize . Take the initiative to understand the usage scenarios and application methods of dynamic planning , And keep practicing , Until you can easily translate your ideas into code . As you can see , It needs to be methodical . We don't have to use advanced algorithms or data structure knowledge to solve problems , Array is enough .

I don't have time to finish / Spatial complexity analysis , You can use it as an exercise after class . Please feel free to leave a message in the comments , Ask questions or share ideas .

Link to the original text ： https://hackernoon.com/all-you-need-to-know-about-dynamic-programming-0tj3e5l This paper is written by AI Translation of science and technology base , Reprint please indicate the source

The source and reprint of the original text are detailed in the text , If there is any infringement , Please contact the yunjia_community@tencent.com Delete .

Original publication time ： 2020-12-01

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

https://chowdera.com/2020/12/20201208142843072q.html