当前位置: 首页 > news >正文

【力扣】62. 不同路径 <动态规划>

【力扣】62. 不同路径

一个机器人位于一个 m m m x n n n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?
在这里插入图片描述

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

示例 2:
输入:m = 3, n = 2
输出:3

解释:
从左上角开始,总共有 3 条路径可以到达右下角。

    1. 向右 -> 向下 -> 向下
    1. 向下 -> 向下 -> 向右
    1. 向下 -> 向右 -> 向下

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

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

提示:
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 1 0 9 10^9 109

题解

  • 确定 dp 数组以及下标的含义
    dp[i][j] :表示从 (0,0) 出发,到 (i, j) 有 dp[i][j] 条不同的路径。
  • 确定递推公式
    想要求 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] 只有这两个方向过来。
  • dp 数组如何初始化
    dp[i][0] 一定都是1,因为从 (0, 0) 的位置到 (i, 0) 的路径只有一条,那么 dp[0][j] 也同理。
  • 确定遍历顺序
    dp[i][j] 都是从其上方和左方推导而来
  • 举例推导 dp 数组(打印 dp 数组)
public class Solution {public static int uniquePaths(int m, int n) {//dp数组定义int[][] dp = new int[m][n];//初始化for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int i = 0; i < n; i++) {dp[0][i] = 1;}//遍历for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
}

相关文章:

【力扣】62. 不同路径 <动态规划>

【力扣】62. 不同路径 一个机器人位于一个 m m m x n n n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xff09;。问总共有多少条…...

【Python小项目】Python的GUI库Tkinter实现随机点名工具或抽奖工具并封装成.exe可执行文件

文章目录 一、项目背景二、需求分析UI界面设计如下:具体需求如下:二、实现思路三、项目关键代码读取excel中的人员名单实现随机滚动抽取主函数中Tkinter的界面相关操作实现窗口相关背景图设置组件相关完整代码四、将程序封装成.exe可执行文件将代码转换成.py文件五、总结与拓…...

【MySql】mysql之基础语句

一、常用的数据类型 类型解释举例int整型用于定义整数类型的数据&#xff08;1、2、3、4、5…&#xff09;float单精度浮点&#xff08;4字节32位&#xff09;准确表示小数点后六位double双精度浮点&#xff08;8字节64位&#xff09;小数位更多&#xff0c;更精确char固定长度…...

使用API调用获取商品数据的完整方案

在电子商务应用程序中&#xff0c;商品详情接口是不可或缺的一部分。它用于从电商平台或自己的数据库中获取商品数据&#xff0c;并将其提供给应用程序的其他部分使用。本文将详细介绍如何设计一个完整的商品详情接口方案&#xff0c;其中包括使用API调用来获取商品数据的过程。…...

来看看入门级别的室内设计创意是怎么样构成的

在这个世界上&#xff0c;信息源源不断地输送给我们&#xff0c;数字通信成为常态&#xff0c;对话的艺术正在逐渐消失&#xff1b;衡量一个人社交成功与否的最佳标准变为点赞数、粉丝数和高参与率&#xff1b;Ai人工智能引发了更快节奏的工作流程&#xff0c;工作要求越来越高…...

Go 面向对象(匿名字段)

概述 严格意义上说&#xff0c;GO语言中没有类(class)的概念,但是我们可以将结构体比作为类&#xff0c;因为在结构体中可以添加属性&#xff08;成员&#xff09;&#xff0c;方法&#xff08;函数&#xff09;。 面向对象编程的好处比较多&#xff0c;我们先来说一下“继承…...

生成式AI,赋能数字劳动力的关键工具

人们认为&#xff0c;生成式人工智能是一种可以让他们用自己的话来提问或生成副本和图像的工具。事实也是如此&#xff0c;人工智能在这两方面上都做的非常好&#xff0c;但让人意想不到的是&#xff0c;它还蕴含着改变我们个人和专业工作的巨大潜力&#xff0c;能帮我们访问、…...

python提取邮件的附件,以excel为例

配置邮箱、读取基本的邮件内容请参考&#xff1a;python读取并解析邮箱邮件&#xff0c;读取邮件主题、内容、时间 以excel为例&#xff1a; 获取邮件&#xff1a; email_value_config {imap_server: imap.exmail.qq.com, username: xxxxxxxx.com, password: xxxxx, }# 连接…...

ZooKeeper技术内幕

文章目录 1、系统模型1.1、数据模型1.2、节点特性1.2.1、节点类型 1.3、版本——保证分布式数据原子性操作1.4、 Watcher——数据变更的通知1.5、ACL——保障数据的安全1.5.1、权限模式&#xff1a;Scheme1.5.2、授权对象&#xff1a;ID1.5.3、权限扩展体系 2、序列化与协议2.1…...

乱糟糟的YOLOv8-detect和pose训练自己的数据集

时代在进步&#xff0c;yolo在进步&#xff0c;我还在踏步&#xff0c;v8我浅搞了一下detect和pose&#xff0c;记录一下&#xff0c;我还是要吐槽一下&#xff0c;为啥子这个模型就放在了这个文件深处&#xff0c;如图。 以下教程只应用于直接应用yolov8&#xff0c;不修改。…...

【Nginx】Nginx $remote_addr和$proxy_add_x_forwarded_for变量详解

$remote_addr 代表客户端IP。注意&#xff0c;这里的客户端指的是直接请求Nginx的客户端&#xff0c;非间接请求的客户端。假设用户请求过程如下&#xff1a; 用户客户端--发送请求->Nginx1 --转发请求-->Nginx2->后端服务器那么&#xff0c;默认情况下&#xff0c;…...

MySQL自动删除binlog日志

MySQL的二进制日志&#xff08;binlog&#xff09;是MySQL用于复制和恢复操作的日志。随着时间的推移&#xff0c;binlog文件可能会快速增长并占用大量的磁盘空间。为了避免磁盘空间耗尽&#xff0c;您可以配置MySQL自动删除旧的binlog文件。 以下是自动删除binlog文件的方法&…...

C++ 文件和流

iostream 标准库提供了 cin 和 cout 方法&#xff0c;用于从标准输入读取流和向标准输出写入流。而从文件中读取流或向文件写入流&#xff0c;需要用到fstream标准库。在 C 中进行文件处理时&#xff0c;须在源代码文件中包含头文件 <iostream> 和 <fstream>。fstr…...

案例分享:西河水库安全监测信息化系统实施方案

一、项目概述1.1项目背景西河水库信息化工作已开展多年&#xff0c;但是由于西河水库监测设备都已经老化或者损坏&#xff0c;现有设备已渐渐不能满足新时期西河水库信息化和现代化发展需求。因此&#xff0c;灌区管理局拟在运用现代信息和通信技术手段感测、分析、整合水库运行…...

使用Angular和MongoDB来构建具有登录功能的博客应用程序

Angular 是一个一站式框架&#xff0c;用于使用相同的可重用代码创建移动和 Web 应用程序。使用 Angular&#xff0c;您可以将整个应用程序划分为可重用的组件&#xff0c;从而更轻松地维护和重用代码。 在本教程系列中&#xff0c;您将学习如何开始使用 Angular 和 MongoDB 作…...

ChatGPT 与前端技术实现制作大屏可视化

像这样的综合案例实分析,我们可以提供案例,维度与指标数据,让ChatGPT与AIGC 帮写出完整代码,并进行一个2行2列的布局设置。 数据与指令如下: 商品名称 销量 目标 完成率 可乐 479 600 79.83% 雪碧 324 600 54.00% 红茶 379 600 63.…...

视频监控/视频云存储EasyCVR平台接入华为ivs3800平台提示400报错,如何解决?

开源EasyDarwin视频监控TSINGSEE青犀视频平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;视频云存储/安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多路视频…...

c++基础数据结构

基础数据结构 目录 • 线性结构 • 二叉堆 • 并查集 • 哈希表 • 应用举例 一、线性结构 基础知识 • 数组 • 带头结点的双链表 – He a d 结点 : 虚拟头结点 – Fir s t 结点 : 第一个有实际内容的结点 • 队列 : 循环队列与 Open-Close 表 例 1. 最…...

微服务-sentinel详解

文章目录 一、前言二、知识点主要构成1、sentinel基本概念1.1、资源1.2、规则 2、sentinel的基本功能2.1、流量控制2.2、熔断降级 3、控制台安装3.1、官网下载jar包3.2、启动控制台 4、项目集成 sentinel4.1、依赖配置4.2、配置文件中配置sentinel控制台地址信息4.3、配置流控4…...

【MTK平台】根据kernel log分析wifi 连接的时候流程

一 概要: 本文主要讲解根据kernel log分析下 当前路径下(vendor/mediatek/kernel_modules/connectivity/wlan/core/gen4m/)wifi scan的时候代码流程 二. Log分析: 2.1)可以知道WiFi在连接的时候先通过scanSearchBssDescByScoreForAis方法扫描捕获到了需要连接的SSID &q…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

深度解析云存储:概念、架构与应用实践

在数据爆炸式增长的时代&#xff0c;传统本地存储因容量限制、管理复杂等问题&#xff0c;已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性&#xff0c;成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理&#xff0c;云存储正重塑数据存储与…...

用鸿蒙HarmonyOS5实现国际象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码&#xff0c;使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...

自定义线程池1.2

自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本&#xff0c;将线程池中的线程数量交给使用者决定&#xff0c;并且将线程的创建延迟到任务提交的时候&#xff0c;在本文中我们将对这个版本进行如下的优化&#xff1a; 在新建线程时交给线程一个任务。让线程在某种情况下…...

MySQL基本操作(续)

第3章&#xff1a;MySQL基本操作&#xff08;续&#xff09; 3.3 表操作 表是关系型数据库中存储数据的基本结构&#xff0c;由行和列组成。在MySQL中&#xff0c;表操作包括创建表、查看表结构、修改表和删除表等。本节将详细介绍这些操作。 3.3.1 创建表 在MySQL中&#…...