LeetCode | 不同路径

一个机器人位于一个 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

思路

在过去,有这样一个词,那就是遇难则反,从起点推导出最小路径和是困难的,那我们就从终点去推导。

解题过程

我们都知道一个方块,只能向右或向下。在初始化dp之后,我们会有这样一条关系式:

d p [ i ] [ j ] = { 1 if  i = = m − 1   a n d   j = = n − 1 d p [ i + 1 ] [ j ] + d p [ i ] [ j + 1 ] if  i + 1 < m   a n d   j + 1 < n d p [ i + 1 ] [ j ] if  i + 1 < m d p [ i ] [ j + 1 ] if   j + 1 < n dp[i][j] = \left\{\begin{matrix} 1 &\text{if } i == m-1 \ and \ j == n-1 \\ dp[i+1][j] + dp[i][j+1]&\text{if } i+1 < m \ and \ j+1 < n \\ dp[i+1][j]&\text{if } i+1 < m \\ dp[i][j+1] &\text{if } \ j+1 < n \end{matrix} \right. dp[i][j]= 1dp[i+1][j]+dp[i][j+1]dp[i+1][j]dp[i][j+1]if i==m1 and j==n1if i+1<m and j+1<nif i+1<mif  j+1<n

复杂度

时间复杂度: O ( N ⋅ M ) O(N \cdot M) O(NM)
空间复杂度: O ( N ⋅ M ) O(N \cdot M) O(NM)

Code

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[120][120];
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                dp[i][j] = 0;
            }
        }
        dp[m-1][n-1] = 1;
        for(int i = m-1; i >= 0; --i) {
            for(int j = n-1; j >= 0; --j) {
                if(i == m-1 && j == n-1) continue;
                if(i+1 < m && j+1 < n) {
                    dp[i][j] = dp[i+1][j] + dp[i][j+1];
                } else {
                    if(i+1 < m) {
                        dp[i][j] = dp[i+1][j];
                    }
                    if(j+1 < n) {
                        dp[i][j] = dp[i][j+1];
                    }
                }
            }
        }
		return dp[0][0];
    }
};

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

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

相关文章

低代码系统-产品架构案例介绍、得帆云(八)

产品名称 得帆云DeCode低代码平台-私有化 得帆云DeMDM主数据管理平台 得帆云DeCode低代码平台-公有云 得帆云DePortal企业门户 得帆云DeFusion融合集成平台 得帆云DeHoop数据中台 名词 概念 云原生 指自己搭建的运维平台&#xff0c;区别于阿里云、腾讯云 Dehoop 指…

使用ensp进行ppp协议综合实验

实验拓扑 实验划分 AR1的Serial3/0/0接口&#xff1a;192.168.1.1/24&#xff1b; AR2的Serial3/0/0接口&#xff1a;192.168.1.2/24&#xff1b; AR2的Serial3/0/1和4/0/0的聚合接口&#xff1a;192.168.2.2/24&#xff1b; AR3的Serial3/0/0和3/0/1的聚合接口&#xff1a;192…

【Python・机器学习】多元回归模型(原理及代码)

前言 自学笔记&#xff0c;分享给语言学/语言教育学方向的&#xff0c;但对语言数据处理感兴趣但是尚未入门&#xff0c;却需要在论文中用到的小伙伴&#xff0c;欢迎大佬们补充或绕道。ps&#xff1a;本文最少限度涉及公式讲解&#xff08;文科生小白友好体质&#xff09;&am…

unity免费资源2025-1-26

https://assetstore.unity.com/packages/tools/animation/motion-warping-climb-interact-270046 兑换码KINEMATION2025

Kitchen Racks 2

Kitchen Racks 2 吸盘置物架 Kitchen Racks-CSDN博客

ESMC-600M蛋白质语言模型本地部署攻略

前言 之前介绍了ESMC-6B模型的网络接口调用方法&#xff0c;但申请token比较慢&#xff0c;有网友问能不能出一个本地部署ESMC小模型的攻略&#xff0c;遂有本文。 其实本地部署并不复杂&#xff0c;官方github上面也比较清楚了。 操作过程 环境配置&#xff1a;CUDA 12.1、…

JAVA设计模式:依赖倒转原则(DIP)在Spring框架中的实践体现

文章目录 一、DIP原则深度解析1.1 核心定义1.2 现实比喻 二、Spring中的DIP实现机制2.1 传统实现 vs Spring实现对比 三、Spring中DIP的完整示例3.1 领域模型定义3.2 具体实现3.3 高层业务类3.4 配置类 四、Spring实现DIP的关键技术4.1 依赖注入方式对比4.2 自动装配注解 五、D…

JVM栈溢出线上环境排查

#查看当前Linux系统进程ID、线程ID、CPU占用率&#xff08;-eo后面跟想要展示的列&#xff09; ps H -eo pid,tid,%cpups H -eo pid,tid,%cpu |grep tid #使用java jstack 查看进程id下所有线程id的情况 jstack pid 案例2 通过jstack 排查死锁问题 #启动java代码 jstack 进…

Langchain+讯飞星火大模型Spark Max调用

1、安装langchain #安装langchain环境 pip install langchain0.3.3 openai -i https://mirrors.aliyun.com/pypi/simple #灵积模型服务 pip install dashscope -i https://mirrors.aliyun.com/pypi/simple #安装第三方集成,就是各种大语言模型 pip install langchain-comm…

Gradle配置指南:深入解析settings.gradle.kts(Kotlin DSL版)

文章目录 Gradle配置指南&#xff1a;深入解析settings.gradle.kts&#xff08;Kotlin DSL版&#xff09;settings.gradle.kts 基础配置选项单项目配置多项目配置 高级配置选项插件管理&#xff08;Plugin Management&#xff09;基础配置模板案例&#xff1a;Android项目标准配…

php twig模板引擎详细使用教程

php twig模板引擎 1. 什么是Twig模板引擎 Twig是一个强大且灵活的PHP模板引擎&#xff0c;它提供了一种更简洁和可扩展的方法来创建PHP应用程序的视图层。Twig模板引擎旨在将设计与业务逻辑分离&#xff0c;并为开发人员提供一种更加清晰和易于维护的方式来构建网页。Twig由S…

Java后端之AOP

AOP&#xff1a;面向切面编程&#xff0c;本质是面向特定方法编程 引入依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId></dependency>示例&#xff1a;记录…

vim的多文件操作

[rootxxx ~]# vim aa.txt bb.txt cc.txt #多文件操作 next #下一个文件 prev #上一个文件 first #第一个文件 last #最后一个文件 快捷键: ctrlshift^ #当前和上个之间切换 说明&#xff1a;快捷键ctrlshift^&#xff0c…

DataSecOps的要点

2020年首次提出&#xff0c;DataSecOps是一种敏捷、全面、内置安全的 方法&#xff0c;用于协调不断变化的数据及其用户&#xff0c;旨在快速提供数据价值&#xff0c; 同时确保数据的私密性、安全性和良好的管理。 强调数据全生命周 期流转运营过程中的内嵌安全属性&#x…

实用工具推荐----wsl安装

一&#xff1a;Win设置修改 Win 搜索 ”启用或关闭windows 功能“ 将如下内容选中 点击升级 重启电脑 二&#xff1a;安装步骤 参考官方文档 适用于 Linux 的 Windows 子系统文档 | Microsoft Learn 下载wsl ubantu发行包 旧版 WSL 的手动安装步骤 | Microsoft Learn 将u…

如何建设一个企业级的数据湖

建设一个企业级的数据湖是一项复杂且系统化的工程&#xff0c;需要从需求分析、技术选型、架构设计到实施运维等多个方面进行综合规划和实施。以下是基于我搜索到的资料&#xff0c;详细阐述如何建设企业级数据湖的步骤和关键要点&#xff1a; 一、需求分析与规划 明确业务需…

如何在 macOS 上安装 PIP ?

PIP 是任何 Python 开发人员必备的工具&#xff0c;因为它简化了安装和管理 Python 包的过程。本教程是为 macOS 用户量身定制的&#xff0c;并假设对使用终端有基本的了解。 必备条件 在安装 PIP 之前&#xff0c;必须确保您的系统上已经安装了 Python。Python 3.4 及更高版…

Kotlin开发(六):Kotlin 数据类,密封类与枚举类

引言 想象一下&#xff0c;你是个 Kotlin 开发者&#xff0c;敲着代码忽然发现业务代码中需要一堆冗长的 POJO 类来传递数据。烦得很&#xff1f;别急&#xff0c;Kotlin 贴心的 数据类 能帮你自动生成 equals、hashCode&#xff0c;直接省时省力&#xff01;再想想需要多种状…

多版本并发控制:MVCC的作用和基本原理

多版本并发控制&#xff1a;MVCC的作用和基本原理 1、MVCC简介1.1 快照读与当前读的区别1.1.1 快照读1.1.2 当前读 1.2 数据库的读写问题1.3 MVCC的作用 2、MVCC实现原理之ReadView2.1 什么是ReadView2.2 ReadView的设计思路2.3 MVCC整体操作流程 1、MVCC简介 1.1 快照读与当前…

Docker—搭建Harbor和阿里云私有仓库

Harbor概述 Harbor是一个开源的企业级Docker Registry管理项目&#xff0c;由VMware公司开发。‌它的主要用途是帮助用户迅速搭建一个企业级的Docker Registry服务&#xff0c;提供比Docker官方公共镜像仓库更为丰富和安全的功能&#xff0c;特别适合企业环境使用。‌12 Harb…