Java 动态规划 Leetcode 62. 不同路径

 

 代码展示:

class Solution {
    public int uniquePaths(int m, int n) {
        //定义dp数组
        //二维数组多增加一行一列,方便对数组进行初始化
        int[][]dp=new int[m+1][n+1];
        //初始化
        dp[0][1]=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][n];
    }
}

        1.状态表示

                我们采用从后往前的方式推导,我们现在想要求dp[i][j]的值,也就是到i,j位置的不同路径条数,由于机器人只能向下和向右移动,所以我们可以从两个地方到达i,j的位置

        (1).我们可以在i-1,j的位置向下移动到达i,j的位置

        (2).我们可以在i,j-1的位置向右移动到达i,j的位置

        而第一种情况,我们首先要到达i-1,j的位置,而到达i-1,j的位置有dp[i-1][j]种不同的路径,第二种情况,我们首先要到达i,j-1的位置,而到达i,j-1的位置有dp[i][j-1]种不同的路径,所以总共的路径有dp[i-1][j]+dp[i][j-1]

        2.状态转移方程

                通过以上的分析我们也得到了状态转移方程,dp[i][j]=dp[i-1][j]+dp[i][j-1]

        3.定义dp数组进行初始化

                我们可以在创建dp数组时添加辅助结点,这样可以使我们的初始化更加的简单。由于该题中的dp数组是二维数组,所以我们可以将dp数组扩充一行一列

        如图是添加辅助结点前后的初始化对比:

         要是不添加辅助结点也可以将数组的第0行和第0列都初始化为1,在该题中辅助结点的意义不大,但在其他的很多题中,辅助结点可以让你的初始化变得格外简单

        4.根据状态转移方程填充数组

        5.返回值

通过以上步骤便可得出答案

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

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

相关文章

基于springboot+Redis的前后端分离项目(七)-【黑马点评】

&#x1f381;&#x1f381;资源文件分享 链接&#xff1a;https://pan.baidu.com/s/1189u6u4icQYHg_9_7ovWmA?pwdeh11 提取码&#xff1a;eh11 发布笔记&#xff0c;点赞&#xff0c;点赞排行 达人探店1、达人探店-发布探店笔记2、 达人探店-查看探店笔记3、 达人探店-点赞功…

《网络安全标准实践指南》(72页)

导读 摘要&#xff1a;为指导网络数据安全风险评估工作&#xff0c;发现数据安全隐患&#xff0c;防范数据安全风险&#xff0c;依据《中华人民共和国网络安全法》《中华人民共和国数据安全法》《中华人民共和国个人信息保护法》等法律法规&#xff0c;参照数据安全相关国家标…

STM32寄存器点亮LED灯

一&#xff1a; 如何寄存器点灯 1&#xff1a;看单片机的原理图 找到LED灯 这个灯是 PB5引脚 看原理图可以看出 让GPIOB5输出低电平 就能点亮那么我们得让打开控制GPIOB5的时钟让GPIOB5 输出模式让GPIOB5低电平 二&#xff1a;看中文参考手册配置寄存器 2.1&#xff1a;打开管…

【Windows】Redis集群部署

集群是如何进行工作的 Redis采用哈希槽来处理数据与节点之间的映射关系&#xff0c;一个集群共有16384 个哈希槽&#xff0c;每个key通过 CRC16算法计算出一个16bit的值&#xff0c;再对16384取模&#xff0c;得到对应的哈希槽&#xff0c;集群通过维护哈希槽与节点的关系来得…

redis与分布式

主从复制 概念 主从复制&#xff0c;是指将一台Redis服务器的数据&#xff0c;复制到其他的Redis服务器。前者称为主节点(Master)&#xff0c;后者称为从节点(Slave)&#xff0c;数据的复制是单向的&#xff0c;只能由主节点到从节点。Master以写为主&#xff0c;Slave 以读为…

MySQL----MHA高可用

文章目录 一、MHA理论1.1什么是 MHA1.2MHA 的组成1.3MHA 的特点 二、MHA的一主两从部署实验设计故障修复步骤&#xff1a; 一、MHA理论 1.1什么是 MHA MHA&#xff08;MasterHigh Availability&#xff09;是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出…

【Django】Django框架使用指南

Django使用指南 作者简介&#xff1a;嗨~博主目前是长安大学软件工程专硕在读&#x1f4d8;&#xff0c;喜欢钻研一些自己感兴趣的计算机技术&#xff0c;求关注&#x1f609;&#xff01; 框架简介&#xff1a;Django是一个基于Python语言的开源Web应用框架&#xff0c;采用 M…

基于STM32FFT(快速傅里叶变换)音频频谱显示功能实现

+ v hezkz17进数字音频系统研究开发交流答疑 一实验效果 二 设计过程 要用C语言实现STM32频谱显示功能,可以按照以下步骤进行操作: 1 确保已经安装好了适当的开发环境和工具链,例如Keil MDK或者GCC工具链。 2 创建一个新的STM32项目,并选择适合的MCU型号。 3 配置G…

【数据挖掘】时间序列教程【九】

第5章 状态空间模型和卡尔曼滤波 状态空间模型通常试图描述具有两个特征的现象 有一个底层系统具有时变的动态关系,因此系统在时间上的“状态”t 与系统在时间的状态t−1有关 .如果我们知道系统在时间上的状态t−1 ,那么我们就有了我们需要知道的一切,以便对当时的状态进行推…

Android Zygote 启动流程

和你一起终身学习&#xff0c;这里是程序员Android 经典好文推荐&#xff0c;通过阅读本文&#xff0c;您将收获以下知识点: Android系统包含netd、servicemanager、surfaceflinger、zygote、media、installd、bootanimation 等基本服务&#xff0c;具体作用请看下图。 Android…

更开放、更高性能、更具规模,闪马智能布局AGI时代

7月6日&#xff0c;2023世界人工智能大会&#xff08;WAIC 2023&#xff09;在上海盛大开幕。本届大会以“智联世界 生成未来”为主题&#xff0c;聚焦通用人工智能发展&#xff0c;共话产业新未来。 8日上午&#xff0c;由上海闪马智能科技有限公司&#xff08;下称“闪马智能…

el-form实现其中一个填写即可的校验

<el-formref"form":model"formData":rules"formRules"label-width"130px"><el-row :gutter"24"><el-col :span"12"><el-form-item label"司机姓名 :" prop"driverName"…

西电_矩阵论_学习笔记

文章目录 【 第一章 线性空间 】【 第二章 范数 】【 第三章 矩阵函数 】【 第四章 矩阵分解 】【 第五章 矩阵特征值估计 】【 第六章 广义逆 】【 考试重点内容总结 】 这是博主2023春季西电所学矩阵论的思维导图&#xff08;软件是幕布&#xff09;&#xff0c;供大家参考&a…

GaussDB OLTP云数据库配套工具DRS

目录 一、前言 二、DRS定义与使用场景 1、DRS定义 2、DRS场景示意图 三、DRS核心功能 1、实时迁移管理 2、实时同步管理 3、备份迁移管理 4、数据订阅管理 5、实时灾备管理 四、小结 一、前言 华为GaussDB云数据库提供了配套的生态工具数据复制服务DRS。 DRS围绕云…

漏洞深度分析 | CVE-2023-36053-Django 表达式拒绝服务

​ 项目介绍 Django 是一个高级 Python Web 框架&#xff0c;鼓励快速开发和简洁、务实的设计。它由经验丰富的开发人员构建&#xff0c;解决了 Web 开发的大部分麻烦&#xff0c;因此您可以专注于编写应用程序&#xff0c;而无需重新发明轮子。它是免费且开源的。 项目地址…

Squid 缓存服务器

Squid 缓存服务器 作为应用层的代理服务软件&#xff0c;Squid 主要提供缓存加速和应用层过滤控制的功能 ☆什么是缓存代理 当客户机通过代理来请求 Web 页面时 指定的代理服务器会先检查自己的缓存&#xff0c;如果缓存中已经有客户机需要访问的页面&#xff0c;则直接将缓…

【考研思维题】【哈希表 || 什么时候用哈希表呢?快速查询的时候】【我们一起60天准备考研算法面试(大全)-第九天 9/60】

专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客&#xff0c;如有问题交流&#xff0c;欢迎评论区留言&#xff0c;一定尽快回复&#xff01;&#xff08;大家可以去看我的专栏&#xff0c;是所有文章的目录&#xff09;   文章字体风格&#xff1a; 红色文字表示&#…

ModaHub魔搭社区:向量数据库Zilliz Cloud删除 Entity和删除 Collection教程

目录 删除单个 Entity 批量删除 Entity 开始前 操作步骤 使用限制 Entity 是指存储在 Zilliz Cloud 集群中的数据实体,包含用于处理、搜索和查询的数据。如果您不再需要某个 Entity,可以执行相关操作将其删除。 本文介绍如何从 Collection 中删除单个或多个 Entity。 …

网络数据包的监听与分析——IP数据报文分析

1. 抓包工具下载 x下面是一个IP数据报的抓包软件——IPtool的蓝奏云下载链接 https://wwix.lanzoue.com/iaGpy11klpnc 2. iptool使用 下载解压之后&#xff0c;右击以管理员身份运行&#xff0c;打开该exe文件即可 然后点击绿色运行就开始捕包了 随便点一个包进去进行分析就可…

JAVA-MAVEN初学者教程(配置、pom.xml、依赖管理等)

目录 认识MAVEN安装&配置MAVENwindows安装MAVENMAVEN的配置本地仓库 localRepository镜像 mirrors代理仓库 respositories代理 proxies IDEA配置MAVEN&#xff08;一个module&#xff09; MAVEN生命周期install下载包 模块的pom.xml坐标gav打包方式 package属性值 properti…