当前位置: 首页 > 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…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...