首页 > 其他分享 >代码随想录——不同路径Ⅱ(Leetcode 63)

代码随想录——不同路径Ⅱ(Leetcode 63)

时间:2024-07-13 10:28:49浏览次数:13  
标签:obstacleGrid 题目 int 随想录 ++ 63 && Leetcode dp

题目链接
在这里插入图片描述

动态规划

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        // 遇到障碍则从(0,0)到达
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++){
            dp[i][0] = 1;
        }
        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++){
            	// 如果没有障碍则dp公式正确执行
                if(obstacleGrid[i][j] == 0){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

本题目是上一篇博客不同路径这道题目的升级版,整体动态规划思路相同,本题多了障碍这一条件约束。

标签:obstacleGrid,题目,int,随想录,++,63,&&,Leetcode,dp
From: https://blog.csdn.net/qq_46574748/article/details/140395751

相关文章

  • 代码随想录——监控二叉树(Leetcode968)不会
    题目链接贪心/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNodeleft,Tr......
  • 【Leetcode--旋转矩阵】
    解题思路:先进行矩阵上下交换,接着对矩阵进行主对角线交换,就可以从上述左图变换为右图。classSolution{  publicvoidrotate(int[][]matrix){    //上下交换    for(inti=0;i<matrix.length/2;i++){      int[]temp=matrix[......
  • 代码随想录day22 组合 | 组合总和III | 电话号码的字母组合 |
    组合组合解题思路利用回溯算法来暴力枚举所有可能性。这里利用了代码随想录的解题模板即可。剪枝方面,由于某些情况下(如k=n)不需要遍历所有的可能性,因此我们要适当修改一下每次循环遍历的元素个数来进行优化知识点回溯心得如果知道如何将此类问题转换为一个n叉树,就会很......
  • 代码随想录算法训练营第八天| leetcode 344、541、卡码网54
    反转字符串 leetcode344classSolution{public:voidreverseString(vector<char>&s){intindex1=0,index2=s.size()-1;chartmp;while(index1<index2){tmp=s[index1];s[index1]=s[index2];......
  • leetcode简单题21 N.104 二叉树的最大深度 rust描述
     //[3,9,20,null,null,15,7]3//[1,null,2]2usestd::rc::Rc;usestd::cell::RefCell;//Definitionforabinarytreenode.#[derive(Debug,PartialEq,Eq)]pubstructTreeNode{pubval:i32,publeft:Option<Rc<RefCell<TreeNode>>......
  • hnust 1963: 邻接矩阵表示法
    hnust1963:邻接矩阵表示法题目描述输入一个图,用邻接矩阵存储,并实现一些操作。拷贝下面的代码,按要求完成其中的FirstAdjVex,NextAdjVex和CreateUDG操作,其他地方不得改动。//邻接矩阵表示图#include<iostream>#include<iomanip>#include<cstdio>usingnamespaces......
  • LeetCode - #93 复原 IP 地址
    文章目录前言1.描述2.示例3.答案关于我们前言本题由于没有合适答案为以往遗留问题,最近有时间将以往遗留问题一一完善。我们社区陆续会将顾毅(Netflix增长黑客,《iOS面试之道》作者,ACE职业健身教练。)的Swift算法题题解整理为文字版以方便大家学习与阅读。......
  • LeetCode 2974. 最小数字游戏(排序)
    题目:2974.最小数字游戏思路:排序后,两个两个取出来进行操作即可classSolution{public:vector<int>numberGame(vector<int>&nums){sort(nums.begin(),nums.end());vector<int>v;for(inti=1;i<nums.size();i+=2){v.pu......
  • 「代码随想录算法训练营」第九天 | 栈与队列 part1
    232.用栈实现队列题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/题目难度:简单文章讲解:https://programmercarl.com/0232.用栈实现队列.html视频讲解:https://www.bilibili.com/video/BV1nY4y1w7VC题目状态:看视频讲解后通过思路:通过两个栈来实现队......
  • 代码随想录算法训练营第10天 | 复习队列和栈
    2024年7月12日题232.用栈实现队列两边倒即可,要出队列就倒到右边去,然后再回来。classMyQueue{Stack<Integer>s1;Stack<Integer>s2;intsize;publicMyQueue(){s1=newStack<>();s2=newStack<>();size=0;}......