当前位置：网站首页>All you want to know about dynamic planning is here!
All you want to know about dynamic planning is here!
20201208 14:29:18 【AI technology base】
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 selfevident . 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(n1) + F(n2)
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（n1） and F（n2）, however F（n1） Again F（n2） and F（n3）. thus ,F（n2） 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 topdown or bottomup 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 bottomup 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 topdown 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 bottomup 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 onedimensional 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 onedimensional arrays , Turn it into several variables .
 Several lines in two dimensional matrix , Maybe we can reduce it to a few onedimensional 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 topdown 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 N1 Step or step N2 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（N1） and f（N2）.
 In order to get f（N1）, We have to find out f（N2） and f（N3）.
 In order to get f（N2）, We have to find out f（N3） and f（N4）.
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（N2）, f（N3）, f（N4）,... ...
 This problem shows us the optimal substructure ： adopt f（N1） and f（N2） 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/climbingstairs/?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（n1）. Again , To calculate s（n1）, You need to s（0）, s（1）,... ...,s（n2）. The same problem requires multiple calculations .
Here's the code for the bottomup 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/longestincreasingsubsequence/?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/uniquebinarysearchtrees/?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 topdown solution is not much different than before ： Find recursion and use cache .
 For bottomup solutions , One 2D An array is enough to hold the result . As I mentioned earlier , One or more onedimensional 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 = （i1, j） and B=（i,j1）. 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 bottomup 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/minimumpathsum/?ref=hackernoon.com）
（2） knapsack problem
Given two arrays of integers val[0..n  1] and wt [0 . .n1], 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 topdown 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 topdown 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 bottomup 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:n1], B[0:n1]) 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: n1], B) and f(A, B[0:n1]) 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[i1] == text2[j1]) dp[i][j] = dp[i1][j1]+1; else dp[i][j] = max(dp[i1][j], dp[i][j1]); } } return dp[n][m]; }
You can try to write and test your solution in the link below .
（ Link address ：https://leetcode.com/problems/longestcommonsubsequence/?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/allyouneedtoknowaboutdynamicprogramming0tj3e5l 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 ： 20201201
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
边栏推荐
 C++ 数字、string和char*的转换
 C++学习——centos7上部署C++开发环境
 C++学习——一步步学会写Makefile
 C++学习——临时对象的产生与优化
 C++学习——对象的引用的用法
 C++编程经验（6）：使用C++风格的类型转换
 Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
 C + + number, string and char * conversion
 C + + Learning  capacity() and resize() in C + +
 C + + Learning  about code performance optimization
猜你喜欢

C + + programming experience (6): using C + + style type conversion

Latest party and government work report ppt  Park ppt

在线身份证号码提取生日工具

Online ID number extraction birthday tool

️野指针？悬空指针？️ 一文带你搞懂！

Field pointer? Dangling pointer? This article will help you understand!

HCNA Routing＆Switching之GVRP

GVRP of hcna Routing & Switching

Seq2Seq实现闲聊机器人

【闲聊机器人】seq2seq模型的原理
随机推荐
 LeetCode 91. 解码方法
 Seq2seq implements chat robot
 [chat robot] principle of seq2seq model
 Leetcode 91. Decoding method
 HCNA Routing＆Switching之GVRP
 GVRP of hcna Routing & Switching
 HDU7016 Random Walk 2
 [Code+＃1]Yazid 的新生舞会
 CF1548C The Three Little Pigs
 HDU7033 Typing Contest
 HDU7016 Random Walk 2
 [code + 1] Yazid's freshman ball
 CF1548C The Three Little Pigs
 HDU7033 Typing Contest
 Qt Creator 自动补齐变慢的解决
 HALCON 20.11：如何处理标定助手品质问题
 HALCON 20.11：标定助手使用注意事项
 Solution of QT creator's automatic replenishment slowing down
 Halcon 20.11: how to deal with the quality problem of calibration assistant
 Halcon 20.11: precautions for use of calibration assistant
 “十大科学技术问题”揭晓！青年科学家50²论坛
 "Top ten scientific and technological issues" announced Young scientists 50 ² forum
 求反转链表
 Reverse linked list
 js的数据类型
 JS data type
 记一次文件读写遇到的bug
 Remember the bug encountered in reading and writing a file
 单例模式
 Singleton mode
 在这个 N 多编程语言争霸的世界，C++ 究竟还有没有未来？
 In this world of N programming languages, is there a future for C + +?
 es6模板字符
 js Promise
 js 数组方法 回顾
 ES6 template characters
 js Promise
 JS array method review
 【Golang】️走进 Go 语言️ 第一课 Hello World
 [golang] go into go language lesson 1 Hello World