【LeetCode75】第六十三题 不同路径

目录

题目:

示例:

分析:

代码:


题目:

示例:

分析:

题目给我们返回地图的长和宽。问我们从地图的左上走到右下有几种方法。我们只能往下走或是往右走。

这个算是简单的二维动态规划题了。

我们先搞清楚一个问题,我们走到某个格子有几种方法,由于我们只能往下走或是往右走,所以我们只能从上方或是左方走来。所以走到某个格子的方法只有两种,那就是从左走来或是从上走来。

而走到本格的上格的方法也是只有两种,那就是本格的上格的上格以及本格的上格的左格。而走到本格的左格也是一样的。那么我们拿二维的dp数组来存放走到对应地图的方法数。

dp[ i ][ j ]的含义就是我们走到地图的 i 行 j 列有几种方法。

那么我们知道走到某格子只能从上面和左边来,所以dp[ i ][ j ] = dp[ i -1 ][ j ] + dp [ i ][ j - 1 ]

这个意思就是走到某格子的方法数等于走到本格上面的方法数以及走到本格左边的方法数。

那么我们的递推公式是需要行-1,列-1,所以我们用递推公式至少得是行大于等于1以及列大于等于1。所以我们要先把行号为0以及列号为0的dp数组都给初始化。

那么我们知道地图中行号为0的是地图矩阵的最上面的一条边,列号为0的是地图矩阵最左边的一条边。而要走到那两条边的格子,都是只有一种方法,所以我们把dp数组都初始化为1。

递推完毕之后返回dp数组的最后一个元素就好了。

代码:

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>dp(m,vector<int>(n,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];}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ生产故障问题分析

1. 问题引发 由某个服务BI-collector-xx队列出现阻塞&#xff0c;影响很整个rabbitMQ集群服务不可用&#xff0c;多个应用MQ生产者服务出现假死状态&#xff0c;系统影响面较广&#xff0c;业务影响很大。当时为了应急处理&#xff0c;恢复系统可用&#xff0c;运维相对粗暴的把…

华为OD机试 - 相同数字组成图形的周长 - 矩阵(Java 2023 B卷 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述四、Java算法源码五、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷&#xff09;》。 刷的越多…

docker容器

虚拟化产品 1.奇居架构 2.原生架构 1.支持仿真虚拟化&#xff08;对系统硬件没有要求&#xff0c;性能最低&#xff09;vmware个人在windows支持 vmware workstationvmware fusion MAC2.全虚拟化产品&#xff0c;直接使用物理硬件、性能高 exic&#xff08;操作系统&#xff0…

CentOS 7 制作openssl 1.1.1w 版本rpm包 —— 筑梦之路

源码下载地址&#xff1a; https://www.openssl.org/source/openssl-1.1.1w.tar.gz 参考之前的文章&#xff1a; openssl 1.1.1L /1.1.1o/1.1.1t rpm包制作——筑梦之路_openssl的rpm包_筑梦之路的博客-CSDN博客 直接上spec文件&#xff1a; Name: openssl Version: 1.1…

【差旅游记】初见乌海湖

哈喽&#xff0c;大家好&#xff0c;我是雷工。 最近在乌海出差&#xff0c;有幸见到了传说中在沙漠中看海的“黄河明珠”——乌海湖。 前段时间一直有点忙&#xff0c;现在有点时间&#xff0c;趁还没忘光&#xff0c;简单整理记录下。 那是在上个月&#xff0c;2023年8月8号…

【大虾送书第十一期】适合新手自学的网络安全基础技能“蓝宝书”:《CTF那些事儿》

目录 &#x1f96e;写在前面 &#x1f96e;内容简介 &#x1f96e;读者对象 &#x1f96e;专家推荐 &#x1f96e;目录 &#x1f96e;文末福利 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &#x1f990;专栏地址&#xff1a;免费送书活动专栏地址 写在前面 CTF比赛是快…

Leetcode 887. 鸡蛋掉落

文章目录 题目代码&#xff08;9.25 首刷看解析&#xff09; 题目 Leetcode 887. 鸡蛋掉落 代码&#xff08;9.25 首刷看解析&#xff09; class Solution { public:unordered_map<int, int> memo;int superEggDrop(int K, int N) {return dp(K, N);}int dp(int k, int…

【从入门到起飞】JavaSE—方法引用

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【The truth that you leave】 &#x1f970;欢迎并且感谢大家指出我的问题 文章目录 &#x1f354;概述&#x1f354;注意&#x1f388;如何确定是否是…

Java实现byte数组与Hex互转

十六进制字符的输出大写字符&#xff1a;0123456789ABCDEF 十六进制字符的输出小写字符&#xff1a;0123456789abcdef下面使用十六进制大写字符。 1、方式1 public class HexStringUtils {private static final char[] HEX_CHAR_TABLE {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,…

LabVIEW在运行时调整表控件列宽

LabVIEW在运行时调整表控件列宽 如何在LabIEW中运行时调整表控件的列宽大小&#xff1f; 在VI运行时&#xff0c;有两种不同的方法可以更改表中列的宽度。首先&#xff0c;可以使用鼠标手动更改它们;其次&#xff0c;可以从框图中以编程方式更改它们。 手动更改列宽 只有在…

Feign 使用篇

Feign是一个声明式的HTTP客户端工具&#xff0c;它简化了在分布式系统中进行服务间通信的过程。开发人员可以使用Feign来定义接口&#xff0c;然后通过该接口来调用远程服务&#xff0c;就像调用本地方法一样简单。 目录 Feign的一些关键特性和概念&#xff1a;openfeign 对比 …

【高云FPGA系列教程(11):MultiButton按键驱动模块移植】

文章目录 1. MultiButton简介2. MultiButton代码获取3. MultiButton移植4. 测试与运行本文是高云FPGA系列教程的第11篇文章。 1. MultiButton简介 MultiButton, 一个小巧简单易用的事件驱动型按键驱动模块,可无限量扩展按键,按键事件的回调异步处理方式可以简化你的程序结构…

https跳过SSL认证时是不是就是不加密的,相当于http?

https跳过SSL认证时是不是就是不加密的,相当于http?&#xff0c;其实不是&#xff0c;HTTPS跳过SSL认证并不相当于HTTP&#xff0c;也不意味着没有加密。请注意以下几点&#xff1a; HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;本质上是在HTTP的基础上…

zabbix

利用一个优秀的监控软件可以: 通过一个友好的界面进行浏览整个网站所有的服务器状态 可以在 Web 前端方便的查看监控数据 可以回溯寻找事故发生时系统的问题和报警情况 zabbix 是什么&#xff1f; zabbix 是一个基于 Web 界面的提供分布式系统监视以及网络监视功能的企业级…

数字人惯性动作捕捉技术服务,激发吉祥物IP创新活力

近日&#xff0c;2023年成都市全国科普日主场活动启动仪式中&#xff0c;全球首发全国首个科普数字人形象大使“科普熊猫”&#xff0c;在大会活动现场&#xff0c;数字人“科普熊猫”结合惯性动作捕捉技术&#xff0c;与现场主持人、观众进行实时互动交流&#xff0c;以虚实结…

maven入门

作用 项目管理工具&#xff1a;依赖管理&#xff0c;项目构建 具体解决的问题 便于添加依赖自动化构建项目多模块开发 相关概念 本地仓库-》私服-》镜像/远程仓库&#xff08;中央仓库&#xff09; 依赖 依赖的范围 compiletestprovidedruntimesystem主程序是否是否否测…

Unity丨自动巡航丨自动寻路丨NPC丨

文章目录 概要功能展示技术细节小结 概要 提示&#xff1a;这里可以添加技术概要 本文功能是制作一个简单的自动巡逻的NPC&#xff0c;随机自动寻路。 功能展示 技术细节 using UnityEngine;public class NPCController : MonoBehaviour {public float moveSpeed 5.0f; // …

LeetCode算法二叉树—116. 填充每个节点的下一个右侧节点指针

目录 116. 填充每个节点的下一个右侧节点指针 题解&#xff1a; 代码&#xff1a; 运行结果&#xff1a; 给定一个 完美二叉树 &#xff0c;其所有叶子节点都在同一层&#xff0c;每个父节点都有两个子节点。二叉树定义如下&#xff1a; struct Node {int val;Node *left;N…

1.(vue3.x+vite)封装组件

前端技术社区总目录(订阅之前请先查看该博客) 关联博客 2.(vue3.x+vite)组件注册并调用 1:创建组件目录package,并创建相关工程结构 2:编写组件内容(index.vue) 3:添加注册组件方法(index.js) 4:添加路由