首页 > 编程语言 >代码随想录算法训练营第36天 | 动态规划基础2:62.不同路径、63.不同路径 II

代码随想录算法训练营第36天 | 动态规划基础2:62.不同路径、63.不同路径 II

时间:2024-07-22 12:39:45浏览次数:14  
标签:obstacleGrid int 路径 随想录 36 range https dp

62.不同路径
https://leetcode.cn/problems/unique-paths/submissions/548656029/
代码随想录
https://programmercarl.com/0062.不同路径.html
63.不同路径 II
https://leetcode.cn/problems/unique-paths-ii/description/
代码随想录
https://programmercarl.com/0063.不同路径II.html#算法公开课
343.整数拆分(一刷跳过)
https://leetcode.cn/problems/integer-break/
代码随想录
https://programmercarl.com/0343.整数拆分.html
96.不同的二叉搜索树(一刷跳过)
https://leetcode.cn/problems/unique-binary-search-trees/description/
代码随想录
https://programmercarl.com/0096.不同的二叉搜索树.html

62.不同路径

题解思路

  • 思路一:动态规划算法:
    • dp[i][j]代表到第i行第j列的格子的可能性;
    • dp[i][j] = dp[i-1][j]+dp[i][j-1]
  • 排列组合计算
    -计算 $ C(m+n-2,m-1) $

题解代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n for _ in range(m)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        count = m-1
        t = m+n-2
        fenmu = m-1
        fenzi = 1
        while count>0:
            fenzi*=t ##分子已知变化
            t-=1

            while fenmu!=0 and fenzi%fenmu==0:###除得尽再除 
                fenzi //= fenmu
                fenmu -=1
            count-=1
        return fenzi

63.不同路径 II

题解思路

  • 和一比只需要多处理几个关于障碍的特殊情况
    • 障碍在起点和终点 直接为0
    • 初始化时,如果出现障碍,剩下的全为0

题解代码

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m =  len(obstacleGrid)
        n = len(obstacleGrid[0])

        ## 绝路不计算
        if obstacleGrid[0][0]==1 or obstacleGrid[-1][-1]:
            return 0

        dp = [[0]*n for _ in range(m)]

        for i in range(n):
            if obstacleGrid[0][i]!=1:
                dp[0][i] = 1
            else:
                break

        for j in range(m):
            if obstacleGrid[j][0]!=1:
                dp[j][0] = 1
            else:
                break

        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j]==1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]

标签:obstacleGrid,int,路径,随想录,36,range,https,dp
From: https://www.cnblogs.com/P201821440041/p/18315801

相关文章

  • ABC363 DEF 题解
    ABC363DEF题解前情提要:赛时过了ABCE。D-PalindromicNumber题目链接其实赛时已经看出了一些性质,但没想完做法,赛后看题解才发现这么简单/fn首先,为了方便,我们不把\(0\)视作回文数(因此需要特判一下\(n=1\)的情况)。下面要证明:\(d\)位回文数有\(10^{\left\lfloor\f......
  • office365.sharepoint 中的 moveto 或 move_to_using_path 是否处于活动状态?
    我正在尝试使用Office365-REST-Python-Client中的示例将文件从一个文件夹移动到另一个文件夹,但它不起作用:fromoffice365.sharepoint.client_contextimportClientContextfromoffice365.sharepoint.files.move_operationsimportMoveOperationsfromtestsimporttest_t......
  • 欧拉图、欧拉路径、欧拉回路
    P7771【模板】欧拉路径欧拉路径的模板题。思路首先判断是否有欧拉路径,然后排序,找出起点,最后dfs找路径。代码细节多,比如要判断一个点是否存在(这个题目不需要)。#include<bits/stdc++.h>usingnamespacestd;constintN=100010;vector<int>e[N];inthead[N],in......
  • 一入循环深似海,代码随想录螺旋矩阵二刷
    代码随想录螺旋矩阵二刷leetcode59来看下螺旋矩阵。螺旋矩阵这道题确实很容易写着写着就绕进去了。首先读下题。给出正整数n,生成n*n的矩阵。我们来看其中一个用例,完成一个圈是需要四个循环去填充。但是四条边填充的时候要始终保持一样的规则,比如左闭右开的规则。那么转几圈呢......
  • AtCoder Beginner Contest 363
    AtCoderBeginnerContest363A-PilingUp每100分显示一个^。现在已知分数,问想要多显示一个^需要再得多少分。模拟题,显示\(i\)个^的最小分数是\(100\timesi\),而当前的^是\([\frac{R}{100}]\),\(R\)是当前的分数。所以答案就是\(([\frac{R}{100}]+1)\times100-R\)#includ......
  • 代码随想录训练营 Day4打卡 链表part02 24. 两两交换链表中的节点 19.删除链表的倒数
    代码随想录训练营Day4打卡链表part02一、力扣24.两两交换链表中的节点给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]算法思路:引入虚......
  • Loj P10064 黑暗城堡 题解 最短路径树记数
    这道题是一道最短路径树问题。首先,什么是最短路径树呢?定义一个图的最短路径树表示一个图上的生成树,且根节点到图上任一点的距离等于原图上两者之间的距离。而不难发现,题目其实是在求图上最短路径树记数。首先,建出最短路径树。枚举每条边,判断边两个端点到根的距离之差是否为......
  • 代码随想录算法训练营第16天 | 二叉树更加进阶
    2024年7月18日用层序遍历巧解题513.找树左下角的值层序遍历的板子一定要熟背。classSolution{publicintfindBottomLeftValue(TreeNoderoot){List<List<Integer>>res=newArrayList<>();//用根左右遍历,每次记录高度intheight=0;......
  • (7-4-03)RRT算法:基于Gazebo仿真的路径规划系统(3)
    (6)函数select_branch实现了RRT_*_FND算法中的选择分支策略,用于删除不再位于路径上的节点及其子节点。它接收当前达到的节点以及先前的路径作为输入,并根据路径更新图中的节点和边。随着节点的移除,函数会实时显示图的变化。最后,它返回更新后的路径。defselect_branch(G:Graph,......
  • 代码随想录算法训练营第15天 | 二叉树进阶
    2024年7月17日平衡二叉树/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNodeleft......