当前位置： 首页 > article >正文

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

article 2025/1/17 17:52:45

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

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

动态规划学习：

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

注意要画树形结构图

2.转成记忆化搜索

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

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

基本就是1:1转换

文章目录

  • 代码随想录 | Day35 | 动态规划 ：最小花费爬楼梯&&不同路径&&不同路径II
    • 746.使用最小花费爬楼梯
    • 62.不同路径
      • 思路：
      • 1.回溯 DFS
      • 2.记忆化搜索
      • 3.动态规划
    • 63.不同路径II
      • 1.回溯DFS
      • 2.记忆化搜索
      • 3.动态规划

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

int dfs(int m,int n)

2.终止条件

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）的路径数量

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

完整代码：

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);
    }
};

//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的说明被计算过了，直接用

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);
    }
};

//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.确定递推公式

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

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

3.dp数组如何初始化

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

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]

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

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];

完整代码

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

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

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);
    }
};

//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跳过本次循环即可

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开始，小细节注意一下就行


http://www.kler.cn/a/370906.html

相关文章：

  • 《银行保险机构数据安全管理办法》正式实施，分类分级、安全评估共筑安全防线
  • Nginx 如何设置 Upgrade-Insecure-Requests 报头 ？
  • 【RDMA学习笔记】1：RDMA（Remote Direct Memory Access）介绍
  • 基于R计算皮尔逊相关系数
  • Banana Pi BPI-RV2 RISC-V路由开发板采用矽昌通信SF2H8898芯片
  • 【WEB】网络传输中的信息安全 - 加密、签名、数字证书与HTTPS
  • 2-133 基于matlab的粒子群算法PSO优化BP神经网络
  • 云手机简述（概况，使用场景，自己部署云手机）
  • LabVIEW汽车状态监测系统
  • 【SSM详细教程】-14-SpringAop超详细讲解
  • 基于SSM+小程序的智慧旅游平台登录管理系统（旅游2）
  • XJ02、消费金融｜消费金融业务模式中的主要主体
  • 刷爆leetcode Day12 DP
  • 基础数据结构——二叉树（深度优先遍历，前序遍历，中序遍历，后序遍历）
  • 【数据结构】顺序表和链表
  • IFC模型文本的含义
  • 【336】基于springboot的社区物资交易互助平台
  • linux查看文件命令
  • 创建型模式-----建造者模式
  • 金蝶云星空采购退料单集成易仓出库单实现高效数据对接
  • 安宝特分享 | AR技术引领：跨国工业远程协作创新模式
  • goalng框架Gin解析
  • Python小白学习教程从入门到入坑------第十八课 异常模块与包【上】（语法基础）
  • VoLTE 微案例：VoLTE 注册失败，I-CSCF 返回 403，HSS(UAR) 返回 5001
  • 鸿蒙HarmonyOS next开发容器类库使用
  • VSCode 设置环境变量（WSL 2）