LeetCode-62. 不同路径【数学 动态规划 组合数学】

LeetCode-62. 不同路径【数学 动态规划 组合数学】

  • 题目描述:
  • 解题思路一:动态规划,动规五部曲
  • 解题思路二:动态规划(版本二)
  • 解题思路三:数论

题目描述:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:
在这里插入图片描述
输入:m = 3, n = 7
输出:28
示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下
    示例 3:

输入:m = 7, n = 3
输出:28
示例 4:

输入:m = 3, n = 3
输出:6

提示:

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

解题思路一:动态规划,动规五部曲

  1. 确定dp数组(dp table)以及下标的含义
    dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。

  2. 确定递推公式
    想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。

此时在回顾一下 dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。

那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

  1. dp数组的初始化
    如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

  2. 确定遍历顺序
    这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

  1. 举例推导dp数组
    如图所示:
    在这里插入图片描述
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 创建一个二维列表用于存储唯一路径数
        dp = [[0] * n for _ in range(m)]
        
        # 设置第一行和第一列的基本情况
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        
        # 计算每个单元格的唯一路径数
        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[m - 1][n - 1]

时间复杂度:O(nm)
空间复杂度:O(nm)

解题思路二:动态规划(版本二)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 创建一个一维列表用于存储每列的唯一路径数
        dp = [1] * n
        
        # 计算每个单元格的唯一路径数
        for j in range(1, m):
            for i in range(1, n):
                dp[i] += dp[i - 1]
        
        # 返回右下角单元格的唯一路径数
        return dp[n - 1]

时间复杂度:O(nm)
空间复杂度:O(n)

解题思路三:数论

在这个图中,可以看出一共m,n的话,无论怎么走,走到终点都需要 m + n - 2 步。
在这里插入图片描述
在这m + n - 2 步中,一定有 m - 1 步是要向下走的,不用管什么时候向下走。

那么有几种走法呢? 可以转化为,给你m + n - 2个不同的数,随便取m - 1个数,有几种取法。

那么这就是一个组合问题了。

那么答案,如图所示:
在这里插入图片描述
求组合的时候,要防止两个int相乘溢出! 所以不能把算式的分子都算出来,分母都算出来再做除法。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        numerator = 1  # 分子
        denominator = m - 1  # 分母
        count = m - 1  # 计数器,表示剩余需要计算的乘积项个数
        t = m + n - 2  # 初始乘积项
        while count > 0:
            numerator *= t  # 计算乘积项的分子部分
            t -= 1  # 递减乘积项
            while denominator != 0 and numerator % denominator == 0:
                numerator //= denominator  # 约简分子
                denominator -= 1  # 递减分母
            count -= 1  # 计数器减1,继续下一项的计算
        return numerator  # 返回最终的唯一路径数

时间复杂度:O(m)
空间复杂度:O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/537612.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

麦肯锡问题分析七步法

麦肯锡七步分析法又称“七步分析法”是麦肯锡公司根据他们做过的大量案例&#xff0c;总结出的一套对商业机遇的分析方法。它是一种在实际运用中&#xff0c;对新创公司及成熟公司都很重要的思维、工作方法。麦肯锡问题分析7步法为企业提供了一个结构化的问题解决框架&#xff…

分类算法(数据挖掘)

目录 1. 逻辑回归&#xff08;Logistic Regression&#xff09; 2. 支持向量机&#xff08;Support Vector Machine, SVM&#xff09; 3. 决策树&#xff08;Decision Tree&#xff09; 4. 随机森林&#xff08;Random Forest&#xff09; 5. K近邻&#xff08;K-Nearest …

Mongodb入门--头歌实验MongoDB 复制集 分片

一、MongoDB之副本集配置 1.1MongoDB主从复制 主从复制是MongoDB最早使用的复制方式&#xff0c; 该复制方式易于配置&#xff0c;并且可以支持任意数量的从节点服务器&#xff0c;与使用单节点模式相比有如下优点&#xff1a; 在从服务器上存储数据副本&#xff0c;提高了数…

【已解决】VMware Horizon Client: 无法建立安全加密链路连接

文章目录 问题原因解决方法方法1&#xff1a;在HTTPS拦截中添加VMware忽略列表 (推荐)方法2&#xff1a; 只拦截 浏览器进程的请求 / 取消 HTTPS 拦截&#xff08;如果没有拦截HTTPS的必要 / 只针对浏览器请求&#xff0c;可以使用此方法&#xff09; 当前使用mac 编辑&#xf…

淘宝扭蛋机小程序:扭出惊喜,乐享购物新体验

在快节奏的现代生活中&#xff0c;人们总是在寻找新鲜、有趣的娱乐方式。淘宝扭蛋机小程序应运而生&#xff0c;为您带来前所未有的购物与娱乐结合新体验。在这里&#xff0c;每一次的扭动都充满惊喜&#xff0c;每一次的点击都带来乐趣&#xff0c;让您在购物的同时&#xff0…

OpenResty,Nginx实现接口验签与黑名单控制

介绍 nginx与openresty是两种优秀知名的7层负载均衡软件&#xff0c;nginx以其出色的性能和稳定性成为首选&#xff0c;而openresty则是在Nginx基础上构建的&#xff0c;支持嵌入Lua语言&#xff0c;大幅提升了开发效率。 安装OpenResty 版本 openresty-1.25.3.1-win64下载地…

D. Solve The Maze Codeforces Round 648 (Div. 2)

题目链接&#xff1a; Problem - 1365D - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/problemset/problem/1365/D 题目大意&#xff1a; 有一张地图n行m列&#xff08;地图外面全是墙&#xff09;&#xff0c…

阿里云服务器配置选择详细指导

云服务器配置如何选择&#xff1f;云服务器配置包括CPU内存、公网带宽和系统盘&#xff0c;阿里云服务器还要注意云服务器规格及轻量应用服务器的选择&#xff0c;云服务器吧以阿里云服务器为例来详细说下小白用户选择云服务器配置攻略&#xff1a; 一、准备工作 如果你不注册…

文献速递:深度学习肝脏肿瘤诊断---基于多相增强 CT 和临床数据的恶性肝肿瘤鉴别诊断深度学习

Title 题目 Deep learning for diferential diagnosisof malignant hepatic tumors based on multi-phase contrast-enhanced CT and clinical data 基于多相增强 CT 和临床数据的恶性肝肿瘤鉴别诊断深度学习 Abstract 摘要 Liver cancer remains the leading cause of can…

2024 年 AI代码助手AI Coding Assistant智能工具

AI代码助手&#xff08;AI Coding Assistant&#xff09;是一种利用人工智能帮助开发人员更快、更准确地编写代码的软件工具。 它可以通过根据提示生成代码或在你实时编写代码时建议自动完成代码来实现此目的。 以下是AI代码助手可以做的一些事情&#xff1a; 与你使用的流行代…

指令集体系简读

这一部分&#xff0c;采用问答的方式来进行梳理&#xff1b; 什么是指令集体系&#xff1f; 指令集体系(Instruction Set Architecture,ISA)是规定处理器的外在行为的一系列内容的统称&#xff0c;它包括&#xff1a; 基本数据类型(data types)、指令(instructions)、寄存器…

Socks5代理IP如何使用?详细教程解析

当我们在互联网上浏览网页、下载文件或者进行在线活动时&#xff0c;隐私和安全问题常常被提及。在这样的环境下&#xff0c;一个有效的解决方案是使用Sock5IP。本教程将向您介绍Sock5IP的使用方法&#xff0c;帮助您保护个人隐私并提升网络安全。 一、什么是Sock5IP&#xff1…

使用了代理IP怎么还会被封?代理IP到底有没有效果?

代理IP作为一种网络工具&#xff0c;被广泛应用于各种场景&#xff0c;例如网络爬虫、海外购物、规避地区限制等。然而&#xff0c;很多用户在使用代理IP的过程中却发现自己的账号被封禁&#xff0c;这让他们不禁产生疑问&#xff1a;使用了代理IP怎么还会被封&#xff1f;代理…

MXNet安装:专业指南与深度解析

一、引言 MXNet是一个高效且灵活的深度学习框架&#xff0c;它支持多种编程语言和平台&#xff0c;并提供了丰富的深度学习算法和工具。随着深度学习技术的广泛应用&#xff0c;MXNet因其出色的性能和易用性受到了越来越多开发者和研究人员的青睐。本文将详细介绍MXNet的安装过…

YOLOV5 分类:利用yolov5进行图像分类

1、前言 之前介绍了yolov5的目标检测示例,这次将介绍yolov5的分类展示 目标检测:YOLOv5 项目:训练代码和参数详细介绍(train)_yolov5训练代码的详解-CSDN博客 yolov5和其他网络的性能对比 yolov5分类的代码部分在这 2、数据集准备 yolov5分类的数据集就是常规的摆放方式…

SpringCloudAlibabaSeate处理分布式事务

SpringCloudAlibabaSeate处理分布式事务 1、部分面试题 微服务boot/cloud做的项目&#xff0c;你不可能只有一个数据库吧&#xff1f;那么多个数据库之间如何处理分布式事务的&#xff1f; 一个场景&#xff1a;在订单支付成功后&#xff0c;交易中心会调用订单中心的服务把订…

如何在公网环境远程管理内网Windows系统部署的MongoDB数据库

文章目录 前言1. 安装数据库2. 内网穿透2.1 安装cpolar内网穿透2.2 创建隧道映射2.3 测试随机公网地址远程连接 3. 配置固定TCP端口地址3.1 保留一个固定的公网TCP端口地址3.2 配置固定公网TCP端口地址3.3 测试固定地址公网远程访问 前言 MongoDB是一个基于分布式文件存储的数…

通讯录项目(用c语言实现)

一.什么是通讯录 通讯录是一种用于存储联系人信息的工具或应用程序。它是一种电子化的地址簿&#xff0c;用于记录和管理个人、机构或组织的联系方式&#xff0c;如姓名、电话号码、电子邮件地址和邮寄地址等。通讯录的目的是方便用户在需要时查找和联系他人。 通讯录通常以列…

DC-DC 5V2A异步升压5V2A输出电源升压芯片2.6-5.5V供电

一、芯片概述&#xff1a; FP6298是一个电流模式升压DC-DC转换器。它是内置PWM电路0.08Ω功率MOSFET&#xff0c;使该调节器高效。内部补偿网络还可以最小化多达6个外部组件计数。误差放大器的非反相输入连接到一个0.6V的精度参考电压&#xff0c;内部的软启动功能可以降低涌入…

【2024最新博客美化教程重置版】在网页中使用L2Dwidget二次元可动人物前端插件,让动漫美女伴随你左右!

&#x1f680; 个人主页 极客小俊 ✍&#x1f3fb; 作者简介&#xff1a;程序猿、设计师、技术分享 &#x1f40b; 希望大家多多支持, 我们一起学习和进步&#xff01; &#x1f3c5; 欢迎评论 ❤️点赞&#x1f4ac;评论 &#x1f4c2;收藏 &#x1f4c2;加关注 L2Dwidget 二次…