首页 > 其他分享 >【力扣】不同路径II(动态规划)

【力扣】不同路径II(动态规划)

时间:2024-03-12 17:26:21浏览次数:28  
标签:vector 力扣 obstacleGrid int 路径 II ++ continue dp

题目描述

image

思路

这道题并不难,常规的动态规划思路,递推公式也并不难想。
但是贴这题的目的是比较一下题解和我的代码在具体实现上的区别;
代码随想录:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
	if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍,直接返回0
            return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
	//dp数组的值全部初始化为0,所以不必再给障碍位置的dp赋值为0
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
	//当没有遇到障碍时,对边界的dp赋值为1,遇到障碍后直接推出循环,
	//这样就很自然地把循环后面的值都设为0了
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;
		//这里,遇到障碍时直接continue跳过,就把这里的dp保留为0了
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

OK,再看看我的代码:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        if(m == 1 || n == 1){
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(obstacleGrid[i][j]){
                        return 0;
                    }
                }
            }
            return 1;
        }
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0] = 1;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(obstacleGrid[i][j]){
                    dp[i][j] = 0;
                    continue;
                }
                //if(i == 0 || j == 0){
                if(i == 0 && j == 0){
                    dp[i][j] = 1;
                    continue;
                }
                if(i == 0 && j != 0){
                    dp[i][j] = dp[i][j-1];
                    continue;
                }
                if(i != 0 && j == 0){
                    dp[i][j] = dp[i-1][j];
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
                //}
            }
        }
        return dp[m-1][n-1];
    }
};

一拖四

标签:vector,力扣,obstacleGrid,int,路径,II,++,continue,dp
From: https://www.cnblogs.com/satsuki26681534/p/18068770

相关文章

  • XLSReadWriteII5--导入XLS
    varFilePath,ic,fn,ZH0,ZH1:string;ExlAPP,Sheet,Range:Variant;Bname:string;Ret,k,i:integer;XLS:TXLSReadWriteII5;beginifRzTreeView1.Selected=nilthenexit;ifRzTreeView1.Selected.Level<2thenbeginshowmessage('---请先选择具体项目!---');exit;......
  • nginx 从一个路径访问另一个路径怎么跳转
    访问stap的路径跳转到根目录下,并且带上之前的参数#rewrite^/stap/(.*)$/$1permanent;访问stap目录代理到下面目录#location/stap/{#rewrite^/stap/(.*)$https://abgg.fxxxuuuppppmppyyai.com/$1permanent;#}访问stap目录代理到下面目录#location/s......
  • 代随想录 第十八天 | ● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 10
    leetcode:513.找树左下角的值-力扣(LeetCode)思路:是找最深左下角的值,不是找左节点最深的值!!遍历深度,判断最大深度,存储后再与下一个相同深度的比较,先左后右,也就是从左到右的顺序来判断的,所以能找到树下左下角的值classSolution{intmaxdepth=0;intresult=0;......
  • 代码随想录算法训练营第四十四天|完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ
    完全背包题目链接:52.携带研究材料(第七期模拟笔试)(kamacoder.com)思路:完全·背包问题和01背包的区别在于同一个物品可以被重复放入,在代码里的区别就是内部遍历背包的for循环由倒序变成了正序。而且如果我们压缩了一维的话,如我的做法,两个for循环的顺序也是无所谓的。#include<i......
  • 代码随想录算法训练营第七天| 454. 四数相加 II 383. 赎金信
    454.四数相加IIhttps://leetcode.cn/problems/4sum-ii/description/、publicintfourSumCount(int[]nums1,int[]nums2,int[]nums3,int[]nums4){intres=0;HashMap<Integer,Integer>map=newHashMap<>();for(inti:nu......
  • 第五节:二叉树相关(反转二叉树[递归/栈]、最大路径和)
    一.反转二叉树一.题目描述  给你一棵二叉树的根节点root,反转这棵二叉树,并返回其根节点。  示例:  leetcode:https://leetcode.cn/problems/invert-binary-tree/description/  难度:【简单】二.思路分析1-递归 1.首先要有递归结束的条件 2.先写......
  • 第六节:动态规划相关(不同路径、礼物最大价值、最长递增子序列)
    一.        二.        三.         !作       者:Yaopengfei(姚鹏飞)博客地址:http://www.cnblogs.com/yaopengfei/声     明1:如有错误,欢迎讨论,请勿谩骂^_^。声     明2:原创博客请在转载......
  • 【力扣】数楼梯(动态规划)(看来高精度不学不行了)
    问题描述思路这个递推公式并不难,n阶台阶的走法数目即为n-1阶的走法数目(再走一节就到了)加上n-2阶的走法数目。当看到部分测试样例WA,而且都是靠后的测试样例而不是随机分散,那么有很大几率是数据类型存储有问题,存不了太大的数,而不是递推公式的问题。想这题一样,当输入的N为500时,......
  • 62. 不同路径c
    intuniquePaths(intm,intn){long**dp=(long**)malloc(sizeof(long*)*(m+10));for(inti=0;i<m+10;i++)dp[i]=(long*)malloc(sizeof(long)*(n+3));for(inti=0;i<=m;i++)dp[i][0]=1;for(inti=0;i<=n;i++)dp[0][i]=1;for(inti=1;i......
  • 代码随想录算法训练营第四十三天|● 1049. 最后一块石头的重量 II ● 494. 目标和
    最后一块石头的重量 II 题目链接:1049.最后一块石头的重量II-力扣(LeetCode)思路:尽可能将石头分成重量相近的两堆,结果一定最小,因此问题可以转换为分割子集。dp[i]的含义是背包容量为i的背包能装下的最大重量,由于题目中最大重量是15000,所以我们申请15001的vector。注意,结果不......