当前位置:网站首页>Path problem before dynamic planning
Path problem before dynamic planning
2022-07-06 15:39:00 【Xiaogeng who loves learning】
Path problem before Dynamic Planning
routing problem : This chapter only talks about different paths (Leecode 62)、 Different paths (Leecode 63)、 Paths and issues (Leedcode 64)
Tips : After writing the article , Directories can be generated automatically , How to generate it, please refer to the help document on the right
List of articles
Preface
Path problem is the prequel of knapsack problem as a classical dynamic programming problem , For understanding dp The thought model of dynamic programming .
One 、 Different path problems (Leecode 62 secondary )
1. Problem description
A robot is in a m x n The top left corner of the grid ( The starting point is marked as “Start” ). The robot can only move down or right one step at a time . The robot tries to reach the bottom right of the grid ( In the figure below, it is marked as “Finish” ). Ask how many different paths there are in total ?
2. Problem analysis
In fact, dynamic problems only need to consider how to define the data structure 、 The meaning of structure 、 Establishment of state transition equation .
2.1 Define the data structure
The question is how many different paths , In this case, you should use dp[m-1][n-1] To express the final result , The example in the last blog is the longest palindrome string , Namely dp[i][j] To express from i To j String ,leedcode 678 The longest increasing subsequence of can be used dp[i] To express , Because it's continuous .
2.2 Interpretation of structural meaning
In this question dp[i][j] It can be interpreted as :i Represents the row of the map ,j Representative column
In the longest palindrome string dp[i][j]:i Is the starting point of palindrome string idx,j Is the end of the palindrome string
The longest increasing subsequence :dp[i] Is the end of the subsequence idx, Because the starting point is the end of the last cycle , So you don't need to define it as a two-dimensional array , Defined as a two-dimensional array to traverse will exceed the time limit , It takes too long
2.3 Establishment of state transition equation
In this question :
Due to the limitation of the topic, we can only go down or to the right Move , So we follow 「 Current optional direction 」 Analyze :
Current location can only 「 Down 」 Move , That is to say dp[i][j] = dp[i-1][j]
Current location can only 「 To the right 」 Move , That is to say dp[i][j] = dp[i][j-1]
The current position can 「 Down 」 Can also 「 To the right 」 Move , That is to say dp[i][j] =dp[i][j-1] + dp[i-1][j]
Derivation process :
dp[i][j] It represents the arrival map grid[i][j] The number of points reaching the path , Then step up : How to get there grid[i][j] spot , There are only two ways : Enter this point from the front point down or to the right , So arrive at grid[i][j] The only way is to arrive dp[i][j-1] The way + arrive dp[i-1][j] The way , From this we can deduce dp[i][j] State transfer equation of :dp[i][j] =dp[i][j-1] + dp[i-1][j]
3. Code display :
The code is as follows ( Example ):
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0]=1;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i>0&&j>0)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
else if(i>0)
{
dp[i][j]=dp[i-1][j];
}
else if(j>0){
dp[i][j]=dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
Two 、 Different path problems ll(Leecode 63 secondary )
1. Problem description
This is a LeetCode Upper 「63. Different paths II」, The difficulty is Medium.
A robot is in a m x n The top left corner of the grid ( The starting point is marked as “Start” ). The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid ( In the figure below, it is marked as “Finish”). Now consider the obstacles in the grid . So how many different paths will there be from the top left corner to the bottom right corner ? Obstacles and empty positions in the grid are used respectively 1 and 0 To express .
2. Problem analysis
In fact, dynamic problems only need to consider how to define the data structure 、 The meaning of structure 、 Establishment of state transition equation .
2.1 Define the data structure
The question is how many different paths , In this case, you should use dp[m-1][n-1] To express the final result
2.2 Interpretation of structural meaning
In this question dp[i][j] It can be interpreted as :i Represents the row of the map ,j Representative column
2.3 Establishment of state transition equation
In this question :
Due to the limitation of the topic, we can only go down or to the right Move , So we follow 「 Current optional direction 」 Analyze :
Current location can only 「 Down 」 Move , That is to say dp[i][j] = dp[i-1][j]
Current location can only 「 To the right 」 Move , That is to say dp[i][j] = dp[i][j-1]
The current position can 「 Down 」 Can also 「 To the right 」 Move , That is to say dp[i][j] =dp[i][j-1] + dp[i-1][j]
Derivation process :
dp[i][j] It represents the arrival map grid[i][j] The number of points reaching the path , Then step up : How to get there grid[i][j] spot , There are only two ways : Enter this point from the front point down or to the right , So arrive at grid[i][j] The only way is to arrive dp[i][j-1] The way + arrive dp[i-1][j] The way , Of course, the difference between this problem and another problem is : Whether the last point can be moved left or right , From this we can deduce dp[i][j] State transfer equation of :dp[i][j] =dp[i][j-1] + dp[i-1][j], The equation of state does not change , But the conditions must be controlled :i>0&&j>0&&obstacleGrid[i-1][j]==0&&obstacleGrid[i][j-1]==0
3. Code display :
The code is as follows ( Example ):
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n=obstacleGrid[0].size();
int m=obstacleGrid.size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0]=1;
if(obstacleGrid[m-1][n-1]==1)
{
return 0;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i>0&&j>0&&obstacleGrid[i-1][j]==0&&obstacleGrid[i][j-1]==0)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
else if(i>0&&obstacleGrid[i-1][j]==0)
{
dp[i][j]=dp[i-1][j];
}
else if(j>0&&obstacleGrid[i][j-1]==0){
dp[i][j]=dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
Two 、 Minimum path sum (Leecode 64 secondary )
1. Problem description
Given a... That contains a nonnegative integer m x n grid grid , Please find a path from the top left corner to the bottom right corner , Make the sum of the numbers on the path the smallest .
explain : You can only move down or right one step at a time
2. Problem analysis
In fact, dynamic problems only need to consider how to define the data structure 、 The meaning of structure 、 Establishment of state transition equation .
2.1 Define the data structure
The question is how many different paths , In this case, you should use dp[m-1][n-1] To express the final result
2.2 Interpretation of structural meaning
In this question dp[i][j] It can be interpreted as :i Represents the row of the map ,j Representative column
2.3 Establishment of state transition equation
In this question :
Due to the limitation of the topic, we can only go down or to the right Move , So we follow 「 Current optional direction 」 Analyze :
Current location can only 「 Down 」 Move , That is to say dp[i][j] = dp[i-1][j]
Current location can only 「 To the right 」 Move , That is to say dp[i][j] = dp[i][j-1]
The current position can 「 Down 」 Can also 「 To the right 」 Move , That is to say dp[i][j] =dp[i][j-1] + dp[i-1][j]
Derivation process :
dp[i][j] It represents the arrival map grid[i][j] The sum of the numbers of points reaching the path , Then step up : How to get there grid[i][j] spot , There are only two ways : Enter this point from the front point down or to the right , You'll get (dp[i][j-1] The sum of the numbers +grid[i][j])、(dp[i-1][j] The sum of the numbers of +grid[i][j]) Two ways , The result of the problem is to find the one with the smallest number , So just find the smallest one in these two ways , because dp[i][j-1]、dp[i-1][j] These two methods are the minimum value before , So the calculation is dp[i][j] Is the smallest . From this we can deduce dp[i][j] State transfer equation of :dp[i][j]=min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
3. Code display :
The code is as follows ( Example ):
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n=grid[0].size();
int m=grid.size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0]=grid[0][0];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i>0&&j>0)
{
dp[i][j]=min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
}
else if(i>0)
{
dp[i][j]=dp[i-1][j]+grid[i][j];
}
else if(j>0){
dp[i][j]=dp[i][j-1]+grid[i][j];
}
}
}
return dp[m-1][n-1];
}
};
summary
In fact, dynamic problems only need to consider how to define the data structure 、 The meaning of structure 、 Establishment of state transition equation .
Most of the data structures are dp[i][j], It is difficult to define dp[i][j] The meaning of 、i The meaning of representation 、j The meaning of representation
State transition equation : In fact, it's about thinking about changes :dp[i][j] and dp[i-1][j]、dp[i][j-1] The relationship between , This needs to be analyzed according to the problem , Analyze through the results of the problem dp[i][j] How to get to the last step of dp[i][j], such as dp[i][j]–> arrive grid[i][j] The minimum sum of numbers ,dp[i-1][j]–> arrive grid[i-1][j] The minimum sum of numbers ,dp[i-1][j]–> arrive grid[i][j-1] The minimum sum of numbers , This is a recursive idea , You can't always think about how to find the smallest one step by step at the beginning , Instead, you just need to find out how to get from the last smallest to the next smallest , This is the idea of recursion .
边栏推荐
- Market trend report, technological innovation and market forecast of pneumonia drugs obtained by Chinese hospitals
- China's earthwork tire market trend report, technical dynamic innovation and market forecast
- STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
- Accounting regulations and professional ethics [5]
- Crawler series (9): item+pipeline data storage
- Es6--- two methods of capturing promise status as failed
- Record of force deduction and question brushing
- Cost accounting [24]
- China chart recorder market trend report, technology dynamic innovation and market forecast
- Hospital privacy screen Industry Research Report - market status analysis and development prospect forecast
猜你喜欢
Stm32 dossiers d'apprentissage: saisie des applications
How to build a nail robot that can automatically reply
LeetCode#19. Delete the penultimate node of the linked list
ucore lab5
What if software testing is too busy to study?
ucore lab7
Automated testing problems you must understand, boutique summary
JS --- all knowledge of JS objects and built-in objects (III)
入门C语言基础问答
UCORE lab5 user process management experiment report
随机推荐
LeetCode#36. Effective Sudoku
How to become a good software tester? A secret that most people don't know
ucore lab7
Accounting regulations and professional ethics [5]
China's PCB connector market trend report, technological innovation and market forecast
0-1背包问题(一)
Interface test interview questions and reference answers, easy to grasp the interviewer
0 - 1 problème de sac à dos (1)
LeetCode#2062. Count vowel substrings in strings
LeetCode#237. Delete nodes in the linked list
用C语言写网页游戏
What if software testing is too busy to study?
LeetCode#19. Delete the penultimate node of the linked list
STM32 learning record: input capture application
Lab 8 file system
0-1背包問題(一)
UCORE LaB6 scheduler experiment report
Preface to the foundations of Hilbert geometry
China earth moving machinery market trend report, technical dynamic innovation and market forecast
UCORE lab5 user process management experiment report