当前位置:网站首页>All you want to know about dynamic planning is here!

All you want to know about dynamic planning is here!

2020-12-08 14:29:18 AI technology base

author | Your DevOps Guy translate | Hot sauce ~, Coordinating editor | Jin Zhaoyu

Produce | AI Technology base

The first figure | Pay to download in visual China

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] = 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 .

( Link address :https://leetcode.com/problems/climbing-stairs/?ref=hackernoon.com)

(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 .

( Link address :https://leetcode.com/problems/longest-increasing-subsequence/?ref=hackernoon.com)

(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[0] = 1;
dp[1] = 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 .

( Link address :https://leetcode.com/problems/unique-binary-search-trees/?ref=hackernoon.com)

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[0].size();
vector<vector<int>> minSum(nrow, vector<int>(ncol, 0));
minSum[0][0] = grid[0][0];
for(int col = 1; col < ncol; ++col)
minSum[0][col] = minSum[0][col - 1] + grid[0][col];
for(int row = 1; row < nrow; ++row)
minSum[row][0] = minSum[row - 1][0] + grid[row][0];
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 .

( Link address :https://leetcode.com/problems/minimum-path-sum/?ref=hackernoon.com)

(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 .

If there is no common subsequence , Then return to 0.

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 .

( Link address :https://leetcode.com/problems/longest-common-subsequence/?ref=hackernoon.com)

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

This article is from WeChat official account. - AI Technology base (rgznai100) , author :Your DevOps Guy

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 .

版权声明
本文为[AI technology base]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201208142843072q.html