代码随想录 | Day35 | 动态规划 ：最小花费爬楼梯&&不同路径&&不同路径II

动态规划应该如何学习？-CSDN博客

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

746.使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

详解在这篇博客，这里不再赘述。

动态规划应该如何学习？-CSDN博客

62.不同路径

62. 不同路径 - 力扣（LeetCode）

思路：

和爬楼梯差不多，爬楼梯是从i-1和i-2往上走，这个是从左边和上边才能走到当前位置

到当前点（m，n）的路径数量为到（m-1，n）的数量加上（m，n-1）的路径数量

到（3,3）的路径数量就是到（2,3）路径和（3,2）路径数量的和然后就会一直递归到（1,2），（2,1）直接返回一条路径

1.回溯 DFS

还是自底向上进行回溯，由当前块（i，j）的上边（i-1，j）和左边（i，j-1）

1.返回值和参数

dfs含义就是到传入的（m，n）位置的所有路径的数量，所以返回int

1
int dfs(int m,int n)

2.终止条件

1
2
3
4
5
6
7
8
if(n<1||m<1)
	return 0;
if(m==1&&n==1)
	return 1;
if(m==1&&n==2)
	return 1;
if(m==2&&n==1)
	return 1;

到小于1的地方路径数量为0

开始位置（1,1）到（1,1），（1,2），（2,1）都是只有一条路径，直接返回1

3.本层逻辑

到当前点（m，n）的路径数量为到（m-1，n）的数量加上（m，n-1）的路径数量

1
return dfs(m-1,n)+dfs(m,n-1);

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	int dfs(int m,int n)
    {   
        if(n<1||m<1)
            return 0;
        if(m==1&&n==1)
            return 1;
        if(m==1&&n==2)
            return 1;
        if(m==2&&n==1)
            return 1;
        return dfs(m-1,n)+dfs(m,n-1);
    }
    int uniquePaths(int m, int n) {
        return dfs(m,n);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//lambda
class Solution {
public:
    int uniquePaths(int m, int n) {
        function<int(int,int)> dfs=[&](int m,int n)->int{
            if(n<1||m<1)
            	return 0;
        	if(m==1&&n==1)
            	return 1;
        	if(m==1&&n==2)
            	return 1;
        	if(m==2&&n==1)
            	return 1;
        	return dfs(m-1,n)+dfs(m,n-1);
        };
        return dfs(m,n);
    }
};

2.记忆化搜索

加入dp数组作为备忘录，初始化dp为-1

每次返回都给dp赋值之后再返回。碰到不是-1的说明被计算过了，直接用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int dfs(int m,int n,vector<vector<int>>& dp)
    {   
        if(n<1||m<1)
            return 0;
        if(m==1&&n==1)
            return dp[m][n]=1;
        if(m==1&&n==2)
            return dp[m][n]=1;
        if(m==2&&n==1)
            return dp[m][n]=1;
        if(dp[m][n]!=-1)
            return dp[m][n];
        return dp[m][n]=dfs(m-1,n,dp)+dfs(m,n-1,dp);
    }
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
        return dfs(m,n,dp);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//lambda
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
        function<int(int,int)> dfs=[&](int m,int n)->int{
            if(n<1||m<1)
                return 0;
            if(m==1&&n==1)
                return dp[m][n]=1;
            if(m==1&&n==2)
                return dp[m][n]=1;
            if(m==2&&n==1)
                return dp[m][n]=1;
            if(dp[m][n]!=-1)
                return dp[m][n];
            return dp[m][n]=dfs(m-1,n)+dfs(m,n-1);
        };
        return dfs(m,n);
    }
};

3.动态规划

1.确定dp数组以及下标的含义

含义就是到达(i,j)的路径数量，即dp[i][j]是到达(i,j)的路径数量

2.确定递推公式

就是到达左边和上边的数量之和

1
dp[i][j]=dp[i][j-1]+dp[i-1][j];

3.dp数组如何初始化

第一行和第一列都是只有1

1
2
3
4
5
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=n;i++)
	dp[1][i]=1;
for(int i=1;i<=m;i++)
	dp[i][1]=1;

4.确定遍历顺序

dp[i][j]=dp[i][j-1]+dp[i-1][j]

要依赖前面的计算结果，所以是从前往后遍历

1
2
3
for(int i=2;i<=m;i++)
	for(int j=2;j<=n;j++)
		dp[i][j]=dp[i][j-1]+dp[i-1][j];

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=n;i++)
            dp[1][i]=1;
        for(int i=1;i<=m;i++)
            dp[i][1]=1;    
        for(int i=2;i<=m;i++)
            for(int j=2;j<=n;j++)
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
        return dp[m][n];
    }
};

63.不同路径II

63. 不同路径 II - 力扣（LeetCode）

思路都一样就说一下怎么处理这个障碍

1.回溯DFS

终止条件多加一个，如果判断当前i，j是1的话那就直接返回0，说明只要经过这条路路径会加0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int dfs(vector<vector<int>> &obstacleGrid,int i,int j)
    {
        if(i<0||j<0)   
            return 0;
        if(obstacleGrid[i][j]==1)
            return 0;
        if(i==0&&j==0)
            return 1;
        if(i==1&&j==0)
            return 1;
        if(i==0&&j==1)
            return 1;
        return dfs(obstacleGrid,i-1,j)+dfs(obstacleGrid,i,j-1);
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]==1)
            return 0;
        return dfs(obstacleGrid,obstacleGrid.size()-1,obstacleGrid[0].size()-1);
    }
};

2.记忆化搜索

就是遇到障碍的时候要先把dp[i][j]赋值为0，这样后面加这块的路径数量只会加0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int dfs(vector<vector<int>> &obstacleGrid,int i,int j,vector<vector<int>> &dp)
    {
        if(i<0||j<0)   
            return 0;
        if(obstacleGrid[i][j]==1)
            return dp[i][j]=0;
        if(i==0&&j==0)
            return dp[i][j]=1;
        if(i==1&&j==0)
            return dp[i][j]=1;
        if(i==0&&j==1)
            return dp[i][j]=1;
        if(dp[i][j]!=-1)
            return dp[i][j];
        return dp[i][j]=dfs(obstacleGrid,i-1,j,dp)+dfs(obstacleGrid,i,j-1,dp);
    }
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]==1)
            return 0;
        vector<vector<int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),-1));
        return dfs(obstacleGrid,obstacleGrid.size()-1,obstacleGrid[0].size()-1,dp);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//lambda
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]==1)
            return 0;
        vector<vector<int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),-1));
        function<int(int,int)> dfs=[&](int i,int j)->int{
            if(i<0||j<0)   
            return 0;
            if(obstacleGrid[i][j]==1)
                return dp[i][j]=0;
            if(i==0&&j==0)
                return dp[i][j]=1;
            if(i==1&&j==0)
                return dp[i][j]=1;
            if(i==0&&j==1)
                return dp[i][j]=1;
            if(dp[i][j]!=-1)
                return dp[i][j];
            return dp[i][j]=dfs(i-1,j)+dfs(i,j-1);
        };
        return dfs(obstacleGrid.size()-1,obstacleGrid[0].size()-1);
    }
};

3.动态规划

1.初始化的时候要判断，第一行和第一列如果遇到障碍，只有障碍前面的是1，后面的都是0

2.由于我们初始化dp全为0，在后面如果遇到障碍直接continue跳过本次循环即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1)
            return 0;
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<n&&obstacleGrid[0][i]!=1;i++)
            dp[0][i]=1;
        for(int i=0;i<m&&obstacleGrid[i][0]!=1;i++)
            dp[i][0]=1;

        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                if(obstacleGrid[i][j]==1)
                    continue;
                else
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
        return dp[m-1][n-1];
    }
};

注：路径是从1开始，路径II是从0开始，小细节注意一下就行