-
Dynamic programming, English: Dynamic Programming, referred to as DP, if a certain problem has many overlapping sub-problems, using dynamic programming is the most effective. Therefore, each state in dynamic programming must be derived from the previous state. This is different from greed. Greedy does not have state derivation, but directly selects the optimal one from the local area. For example: there are N items and a backpack that can carry a maximum weight of W. The weight of the i-th item is weight[i], and the obtained value is value[i]. Each item can only be used once. Find out which items should be put into the backpack with the highest total value. In dynamic programming, dp[j] is derived from dp[j-weight[i]], and then max(dp[j], dp[j – weight[i]] + value[i]) is taken. But if you are greedy, just choose the largest or smallest item every time you take it. It has nothing to do with the previous state.
-
The state transition formula (recursion formula) is very important, but the dynamic rule is not only the recursion formula. For the dynamic programming problem, I will break it down into the following five steps. Only when these five steps are understood can we say that we have truly mastered dynamic programming!
- Determine the meaning of dp array (dp table) and subscripts
- Determine the recurrence formula
- How to initialize dp array
- Determine the traversal order
- Deriving the dp array with an example
-
**Because in some cases, the recursive formula determines how to initialize the dp array! **When writing dynamic questions, it is normal to have problems with the code! The best way to find the problem is to print out the dp array and see if it is deduced according to your own ideas! Some students’ learning of dp is in a black box state. They don’t know the meaning of the dp array and why it is initialized in this way. They have memorized the recursion formula and wrote the traversal sequence just like this out of habit. Then they write the code in one go. If the code If you can pass it, everything will be fine. If you can’t pass it, just make changes based on your feeling.
Topic: Fibonacci Numbers
-
The sequence of Fibonacci numbers (usually represented by
F(n)) is called the Fibonacci sequence . The sequence starts with0and1, and each subsequent number is the sum of the previous two numbers. That is: F(0) = 0, F(1) = 1; F(n) = F(n – 1) + F(n – 2), where n > 1 -
class Solution {<!-- --> public: int fib(int n) {<!-- --> if(n<2){<!-- --> return n; } int res=fib(n-1) + fib(n-2); return res; } }; -
Time complexity: O(2^n); Space complexity: O(n), including the space occupied by the system stack that implements recursion in the programming language
-
Dynamic programming: Here we need to use a one-dimensional dp array to save the recursive results; determine the meaning of the dp array and the subscript, dp[i] is defined as: Fibonacci of the i-th number The value is dp[i]
- Determine the recursion formula: state transition equation dp[i] = dp[i – 1] + dp[i – 2];
- How to initialize the dp array: dp[0] = 0; dp[1] = 1;
- Determine the traversal order: It can be seen from the recursive formula dp[i] = dp[i – 1] + dp[i – 2]; that dp[i] depends on dp[i – 1] and dp[i – 2] , then the order of traversal must be from front to back.
- Example to derive dp array
-
class Solution {<!-- --> public: int fib(int n) {<!-- --> if(n<2){<!-- --> return n; } vector<int> dp(n + 1,0); dp[1]=1; for(int i=2;i<dp.size();i + + ){<!-- --> dp[i]=dp[i-1] + dp[i-2]; } return dp[dp.size()-1]; } }; -
Time complexity: O(n); Space complexity: O(n)
-
if(n<2){<!-- --> return n; } int dp[2]={<!-- -->0,1}; for(int i=2;i<n + 1;i + + ){<!-- --> dp[i%2]=dp[0] + dp[1]; } return dp[(n)%2]; -
Time complexity: O(n); Space complexity: O(1)
Topic: Climbing stairs
-
Suppose you are climbing stairs. It takes
nsteps before you can reach the top. You can climb1or2steps at a time. How many different ways can you climb to the top of a building? -
There is one way to climb the stairs to the first floor, and there are two ways to climb the stairs to the second floor. Then take two more steps on the first flight of stairs to reach the third floor, and one more step on the second flight of stairs to reach the third floor. Therefore, the status of the stairs to the third floor can be deduced from the status of the stairs to the second floor and the stairs to the first floor, then you can think of dynamic programming. At this point everyone should have discovered that this is the Fibonacci sequence!
-
class Solution {<!-- --> public: int climbStairs(int n) {<!-- --> if(n<3){<!-- --> return n; } int dp[2]={<!-- -->1,2}; for(int i=2;i<n;i + + ){<!-- --> dp[i%2]=dp[0] + dp[1]; } return dp[(n-1)%2]; } }; -
Many of the dynamic rules questions that will be explained later are actually because the current state depends on the first two or three states, and they can all be optimized in terms of space.But I personally think that it is enough to be able to write version one during the interview. Ha, that’s clear. If the interviewer asks for further optimization of the space, we will optimize it.
Topic: Climb the stairs with minimum cost
-
You are given an array of integers
cost, wherecost[i]is the cost of climbing up theith step of the staircase. Once you pay this fee, you have the option of climbing up one or two steps. You can choose to start climbing the stairs from the step indexed0or the step indexed1. Please calculate and return the minimum cost to reach the top of the stairs.- Determine the meaning of the dp array and subscripts: This question only requires a one-dimensional array dp[i]. Definition of dp[i]: The minimum physical effort required to reach the i-th step is dp[i].
- Determine the recursion formula: There are two ways to get dp[i], one is dp[i-1] and the other is dp[i-2]. It costs dp[i – 1] + cost[i – 1] to jump from dp[i – 1] to dp[i]. It costs dp[i – 2] + cost[i – 2] to jump from dp[i – 2] to dp[i]. The smallest one must be chosen, sodp[i] = min(dp[i – 1] + cost[i – 1], dp[i – 2] + cost[i – 2]);
- How to initialize the dp array: Look at the recursive formula. dp[i] is derived from dp[i – 1], dp[i – 2]. Since it is impossible to initialize all dp[i], then only initialize dp[0] and dp[1] are enough, and the others are eventually pushed out by dp[0]dp[1]. The title description clearly states that “You can choose to start climbing the stairs from the step with subscript 0 or subscript 1.” In other words, it is free to reach the 0th step, but if you jump up from the 0th step , it costs cost[0]. So initialize dp[0] = 0, dp[1] = 0;
-
class Solution {<!-- --> public: int minCostClimbingStairs(vector<int> & amp; cost) {<!-- --> if(cost.size()<3){<!-- --> return min(cost[0],cost[1]); } vector<int> dp(cost.size() + 1,0); for(int i=2;i<dp.size();i + + ){<!-- --> dp[i]=min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]); } return dp[cost.size()]; } };
Title: Different paths
-
A robot is located in the upper left corner of a
m x ngrid (the start point is marked “Start” in the image below). The robot can only move one step down or to the right at a time. The robot attempts to reach the lower right corner of the grid (labeled “Finish” in the image below). How many different paths are there in total? -
When looking at this question, the most intuitive idea is to use deep search in graph theory to enumerate how many paths there are. Note that the question says that the robot can only move one step down or to the right at a time. In fact, the path traveled by the robot can be abstracted as a binary tree, and the leaf node is the end point!
-
class Solution {<!-- --> public: int track(int i,int j,int m,int n){<!-- --> if(i>m||j>n){<!-- --> return 0; } if(i==m & amp; & amp; j==n){<!-- --> return 1; } return track(i + 1,j,m,n) + track(i,j + 1,m,n); } int uniquePaths(int m, int n) {<!-- --> return track(0,0,m-1,n-1); } };//time out -
The number of nodes in the binary tree is 2^(m + n – 1) – 1. It can be understood that the deep search algorithm traverses the entire full binary tree (actually it does not traverse the entire full binary tree, it is just an approximation); the time complexity of the deep search code is O(2^(m + n – 1) – 1), you can see Out, this is an exponential time complexity, which is very large.
-
Dynamic programming: The robot starts from the position (0, 0) and reaches the end point (m – 1, n – 1).
- Determine the meaning of the dp array (dp table) and the subscripts: dp[i][j]: Indicates that starting from (0, 0), there are dp[i][j] different paths to (i, j).
- Determine the recursion formula: If you want to ask for dp[i][j], there are only two directions to derive it, namely dp[i – 1] [j] and dp[i] [j – 1]. Then it is natural, dp[i][j] = dp[i – 1] [j] + dp[i] [j – 1], because dp[i][j] only comes from these two directions.
- Initialization of dp array: First of all, dp[i][0] must be 1, because there is only one path from the position of (0, 0) to (i, 0), then the same is true for dp[0][j].
- Determine the traversal order: dp[i][j] are derived from above and to the left, so just traverse layer by layer from left to right.
-
class Solution {<!-- --> public: int uniquePaths(int m, int n) {<!-- --> vector<vector<int>> dp(m,vector<int>(n,1)); for(int i=1;i<m;i + + ){<!-- --> for(int j=1;j<n;j + + ){<!-- --> dp[i][j]=dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } }; -
Time complexity: O(m × n); Space complexity: O(m × n)
-
If there are m and n in total, no matter how you go, it will take m + n – 2 steps to reach the end. Among these m + n – 2 steps, there must be m – 1 steps to go down, no matter when to go down. It can be transformed into, giving you m + n – 2 different numbers, and you can choose m – 1 number at will. There are several ways to choose it. Then this is acombination question. When seeking a combination, you must prevent the multiplication of two ints from overflowing! Therefore, you cannot calculate the numerator and denominator of the equation and then divide it. When calculating the numerator, you need to continuously divide by the denominator. The code is as follows:
-
class Solution {<!-- --> public: int uniquePaths(int m, int n) {<!-- --> long long son=1; int mom=m-1; int count=m-1; int t=m + n-2; while(count--){<!-- --> son *= t--; while(mom!=0 & amp; & amp; son%mom==0){<!-- --> son /= mom; mom--; } } return son; } };
-
Title: Different Paths II
-
A robot is located in the upper left corner of a
m x ngrid (the start point is marked “Start” in the image below). The robot can only move one step down or to the right at a time. The robot attempts to reach the lower right corner of the grid (labeled “Finish” in the image below). Now consider that there are obstacles in the grid. So how many different paths will there be from the upper left corner to the lower right corner? Obstacles and empty locations in the grid are represented by1and0respectively. -
Number theory solution is totally impossible, there is more than one obstacle
-
class Solution {<!-- --> public: int uniquePathsWithObstacles(vector<vector<int>> & amp; obstacleGrid) {<!-- --> int flag =0; int temp_m=0,temp_n=0; for(int i=0;i<obstacleGrid.size();i + + ){<!-- --> for(int j=0;j<obstacleGrid[0].size();j + + ){<!-- --> if(obstacleGrid[i][j]){<!-- --> temp_m=i; temp_n=j; flag=1; break; } } } int count_sum=obstacleGrid.size()-1; long long son_sum=1; int mom_sum=obstacleGrid.size()-1; int mn=obstacleGrid.size() + obstacleGrid[0].size()-2; while(count_sum--){<!-- --> son_sum *= mn--; while(mom_sum!=0 & amp; & amp; son_sum%mom_sum==0){<!-- --> son_sum /= mom_sum; mom_sum--; } } if(flag==0){<!-- --> return son_sum; } long long son1=1; int mom1 = temp_m; int count =temp_m; int mn1 = temp_m + temp_n; while(count--){<!-- --> son1 *= mn1--; while(mom1!=0 & amp; & amp; son1%mom1==0){<!-- --> son1 /= mom1; mom1--; } } long long son2=1; int mom2 = obstacleGrid.size()-temp_m-1; int count2 = obstacleGrid.size()-temp_m-1; int mn2 = obstacleGrid.size()-temp_m + obstacleGrid[0].size()-temp_n-2; while(count2--){<!-- --> son2 *= mn2--; while(mom2!=0 & amp; & amp; son2%mom2==0){<!-- --> son2 /= mom2; mom2--; } } return son_sum-son1*son2; } };//
-
-
Dynamic programming: Determine the meaning of dp array (dp table) and subscripts, dp[i][j]: means starting from (0, 0), there are dp[i][j] different paths to (i, j) .
-
Determine the recursion formula: dp[i][j] = dp[i – 1] [j] + dp[i] [j – 1]. Because there are obstacles, (i, j) should maintain the initial state (the initial state is 0) if it is an obstacle.
-
How to initialize the dp array: There is only one path from the position of (0, 0) to (i, 0), so dp[i] [0] must be 1, and the same is true for dp[0] [j]. But if there is an obstacle on the edge (i, 0), the position after the obstacle (including the obstacle) will be unreachable, so dp[i] [0] after the obstacle should still be the initial value 0.
-
class Solution {<!-- --> public: int uniquePathsWithObstacles(vector<vector<int>> & amp; obstacleGrid) {<!-- --> int m=obstacleGrid.size(); int n=obstacleGrid[0].size(); if(obstacleGrid[m-1][n-1]==1 || obstacleGrid[0][0]==1){<!-- --> return 0; } vector<vector<int>> dp(m,vector<int>(n,0)); for(int i=0;i<m & amp; & amp;obstacleGrid[i][0]==0;i + + ){<!-- --> dp[i][0]=1; } for(int i=0;i<n & amp; & amp;obstacleGrid[0][i]==0;i + + ){<!-- --> dp[0][i]=1; } for(int i=1;i<m;i + + ){<!-- --> for(int j=1;j<n;j + + ){<!-- --> if(obstacleGrid[i][j]==1){<!-- --> continue; } dp[i][j]=dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } }; -
Time complexity: O(n × m), n and m are the length and width of obstacleGrid respectively; Space complexity: O(n × m)
Topic: Integer splitting
-
Given a positive integer
n, split it into the sum ofkpositive integers (k >= 2) and maximize the product of these integers. Returns the maximum product you can get . -
Determine the meaning of the dp array (dp table) and the subscripts: dp[i]: Split the number i, and the maximum product that can be obtained is dp[i]. The definition of dp[i] will be implemented throughout the problem-solving process. If you don’t understand any of the following steps, just think about what dp[i] actually represents!
-
Determine the recursion formula: In fact, you can traverse j from 1, and then there are two channels to get dp[i]. One is to directly multiply j * (i – j). One is j * dp[i – j], which is equivalent to splitting (i – j). If you don’t understand this split, you can recall the definition of dp array. j starts traversing from 1, and the situation of splitting j is actually calculated during the process of traversing j. Then traverse j from 1, compare (i – j) * j and dp[i – j] * j and take the largest one. Recursion formula: dp[i] = max(dp[i], max((i – j) * j, dp[i – j] * j)); It can also be understood that j * (i – j) is Simply split the integer into two numbers and multiply them, while j * dp[i – j] is split into two and multiply more than two numbers. So the recursion formula: dp[i] = max({dp[i], (i – j) * j, dp[i – j] * j});
-
Initialization of dp: Here I only initialize dp[2] = 1. From the definition of dp[i], split the number 2, and the maximum product obtained is 1
-
class Solution {<!-- --> public: int integerBreak(int n) {<!-- --> vector<int> dp(n + 1); dp[2]=1; for(int i=3;i<=n;i + + ){<!-- --> for(int j=1;j<=i/2;j + + ){<!-- --> dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j)); } } return dp[n]; } }; -
Time complexity: O(n^2); Space complexity: O(n)
Topic: Different binary search trees
-
Given an integer
n, find that it consists of exactlynnodes and the node values are from1ton. How many types of the same binary search tree are there? Returns the number of binary search trees that satisfy the question. -
When n is 1, there is one tree, and when n is 2, there are two trees. Let’s take a look at when n is 3.
-
- The number of search trees where element 1 is the head node = the number of search trees where the right subtree has 2 elements * the number of search trees where the left subtree has 0 elements
- The number of search trees where element 2 is the head node = the number of search trees where the right subtree has 1 element * the number of search trees where the left subtree has 1 element
- The number of search trees with element 3 as the head node = the number of search trees with 0 elements in the right subtree * the number of search trees with 2 elements in the left subtree
-
Determine the meaning of the dp array (dp table) and the subscripts: dp[i]: The number of binary search trees composed of nodes from 1 to i is dp[i]. It can also be understood that the number of binary search trees composed of i different element nodes is dp[i], which is the same.
-
Determine the recursion formula: dp[i] + = dp[the number of left subtree nodes with j as the head node] * dp[the number of right subtree nodes with j as the head node]; j is equivalent to the element of the head node, Traverse from 1 to i. So the recursion formula: dp[i] + = dp[j – 1] * dp[i – j]; , j-1 is the number of left subtree nodes with j as the head node, i-j is the number of right subtree nodes with j as the head node Number of subtree nodes
-
How to initialize the dp array: By definition, an empty node is also a binary tree and a binary search tree, which makes sense. From a recursive formula, dp[the number of left subtree nodes with j as the head node] * dp[the number of right subtree nodes with j as the head node], the number of left subtree nodes with j as the head node is 0, It is also required that dp[number of left subtree nodes with j as the head node] = 1, otherwise the results of multiplication will become 0.
-
class Solution {<!-- --> public: int numTrees(int n) {<!-- --> vector<int> dp(n + 1); dp[0]=1; for(int i=1;i<=n;i + + ){<!-- --> for(int j=1;j<=i;j + + ){<!-- --> dp[i] + = dp[j-1]*dp[i-j]; } } return dp[n]; } }; -
time complexity:
O
(
n
2
)
O(n^2)
O(n2); space complexity:
O
(
n
)
O(n)
O(n)
