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

js版 力扣 62. 不同路径

一、题目描述

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

示例 1:

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

示例 2:

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

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

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

  2. 向下 -> 向下 -> 向右

  3. 向下 -> 向右 -> 向下

 

二、思路及回顾

由于机器人只能向下和向右移动,所以二维数组中第一行和第一列永远只有一种走法

假设终点在第二行第二列(图中鼠标),通过推导我们可以得知有两种走法,用二维数组表示这两种走法可以得出,假设终点用f[ i ][ j ],它只能在终点的左边f[ i  ][ j-1 ](即第二行第一列)或者终点上边f[ i-1 ][ j ](即第一行第二列)进入终点,则这两种走法就是该点的两种路径,再看看其他的点也满足这条件:不管怎么走,最后的路径都是在该点的左边或是上边进入。

由此可以推导出状态方程:f[ i ][ j ] = f[ i  ][ j-1 ] + f[ i-1 ][ j ]

现在定义 js二维数组可以用数组方法

const f = new Array(m).fill(0).map(() => new Array(n).fill(0));

解动态规划的步骤

 1. 根据重叠问题定义状态

 2. 寻找最优子结构推导状态方程

 3. 确定dp初始状态

 4. 确定输出值

三、代码展示

var uniquePaths = function(m, n) {const f = new Array(m).fill(0).map(() => new Array(n).fill(0));  // 初始化数组// 初始化行for(let i = 0; i < m; i++) {f[i][0] = 1;}// 初始化列for(let j = 0; j < n; j++) {f[0][j] = 1}for(let i = 1; i < m; i++) {for(let j = 1; j < n; j++) {f[i][j] = f[i][j-1] + f[i-1][j] // 确定状态方程}}return f[m-1][n-1]                 // 确定最终值
}

相关文章:

js版 力扣 62. 不同路径

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

Qt音视频开发16-通用悬浮按钮工具栏的设计

一、前言 通用悬浮按钮工具栏这个功能经过了好几个版本的迭代&#xff0c;一开始设计的时候是写在视频控件widget窗体中&#xff0c;当时功能简单就放一排按钮在顶部悬浮widget中就好&#xff0c;随着用户需求的变化&#xff0c;用户需要自定义悬浮条的要求越发强烈&#xff0…...

商品比价API使用说明

商品数据分析 国内最早的比价搜索平台&#xff0c;专注于电商大数据的分析&#xff0c;有10年技术和数据沉淀。 公司自主研发的爬虫、搜索引擎、分布式计算等技术&#xff0c; 实现了对海量电商数据的及时监测、清洗和统计。 数据丰富 详细使用api 数据采集维度&#xff…...

基于 TensorFlow 的植物识别教程

首先&#xff0c;需要准备一些训练数据集。这些数据集应该包含两个文件夹&#xff1a;一个用于训练数据&#xff0c;另一个用于测试数据。每个文件夹应该包含子文件夹&#xff0c;每个子文件夹对应一个植物的种类&#xff0c;并包含该植物的图像。接下来&#xff0c;我们需要使…...

渗透测试之主机探测存活性实验

渗透测试之主机探测存活性实验实验目的一、实验原理1.1 TCP/IP协议1. TCP2. IP1.2 Ping的原理二、实验环境2.1 操作机器2.2 实验工具三、实验步骤1. 学会使用ping命令2. 使用Nmap进行多种方式的探测总结实验目的 熟悉TCP/IP协议、Ping命令基本概念学习nmap、SuperScan扫描方式…...

好用的idea插件leetcode editor【详细安装指南】

如果你和我一样存在着如下困扰&#xff1a; 上班想摸鱼刷leetcode&#xff0c;但是直接打开leetcode界面太扎眼了或者为leetcode刷题不可以debug而发愁 那今天分享的一款IDEA插件可以统统解决上述问题&#xff0c;插件名字叫leetcode editor&#xff0c;你可以直接在plugins中…...

二氧化碳地质封存技术应用前景及模型构建实践方法与讨论

2022年七月七日&#xff0c;工业和信息化部、发展改革委、生态环境部关于印发工业领域碳达峰实施方案的通知落地。全国各省份积极响应&#xff0c;纷纷出台地方指导文件&#xff0c;标志着我国碳减排事业的全面铺开。二氧化碳地质封存技术作为实现我国“双碳”目标的重要一环&a…...

STM32开发(12)----CubeMX配置WWDG

CubeMX配置窗口看门狗&#xff08;WWDG&#xff09;前言一、窗口看门狗的介绍二、实验过程1.STM32CubeMX配置窗口看门狗2.代码实现3.硬件连接4.实验结果总结前言 本章介绍使用STM32CubeMX对窗口看门狗定时器进行配置的方法。门狗本质上是一个定时器&#xff0c;提供了更高的安…...

JVM18运行时参数

4. JVM 运行时参数 4.1. JVM 参数选项 官网地址&#xff1a;https://docs.oracle.com/javase/8/docs/technotes/tools/windows/java.html 4.1.1. 类型一&#xff1a;标准参数选项 > java -help 用法: java [-options] class [args...](执行类)或 java [-options] -jar …...

Cesium集成WebXR_连接VR设备

Cesium集成WebXR 文章目录Cesium集成WebXR1. 需求2. 技术基础2.1 WebGL2.2 WebXR2.3 其他3. 示例代码4. 效果图5. 参考链接1. 需求 通过WebXR接口&#xff0c;将浏览器端连接到VR头盔&#xff0c;实现在VR头盔中浏览Cesium场景&#xff0c;并可将头盔旋转的操作同步映射为场景…...

物联网在物流行业中的应用

物流管理需要同时监控供应链、仓储、运输等多项活动&#xff0c;然而许多因素会影响物流流程本身并导致延迟。为了简化流程和提高客户满意度&#xff0c;一些行业领导者和决策者积极创新&#xff0c;不断评估并使用物联网对物流流程的成本效益进行深入优化。在本文中&#xff0…...

<c++> 类与对象 | 面向对象 | 访问说明符 | 类的声明 | 创建类

文章目录前言面向过程编程面向对象编程什么是类类和结构体有什么区别三个访问说明符如何创建一个类类的声明创建类申明和定义全部放在类中声明和定义分离前言 从这里我们正式开始学习c中的面向对象编程&#xff0c;在学习之前&#xff0c;我们有必要了解一下什么是面向对象编程…...

恭喜!龙蜥社区荣登 2022 科创中国“开源创新榜”

2 月 20 日&#xff0c;中国科协召开以“创新提振发展信心&#xff0c;科技激发产业活力”为主题的2023“科创中国”年度会议。会上&#xff0c;“科创中国”联合体理事长、中国工程院院士周济介绍了 2022 年系列榜单征集遴选情况&#xff0c;并与中国科协副主席、中国工程院院…...

2023双非计算机硕士应战秋招算法岗之机器学习基础知识

目录 特征工程 2 缺失值处理 15 评价指标 33 逻辑回归 37 决策树 40 随机森林 46 SVM 49 Knn 56 Kmeans 59 PCA 66 朴素贝叶斯 68 常见分类算法的优缺点 72 特征工程 1.什么是特征工程 有这么一句话在业界广泛流传&#xff0c;数据和特征决定了机器学习的上限&#xff0c;而模型…...

二、TS的基础类型、类型注解

TS的基础类型、类型注解 TS的基础类型 js的数据类型&#xff1a; 基础数据类型&#xff08;7个&#xff09; boolean string number null undefined BigInt Symbol 引用数据类型&#xff08;1个&#xff09; Object 变量后面多了一个注解&#xff0c;注解为变量限定数据类型&…...

3年经验,3轮技术面+1轮HR面,拿下字节30k*16薪offer,这些自动化测试面试题值得大家借鉴

面试一般分为技术面和hr面&#xff0c;形式的话很少有群面&#xff0c;少部分企业可能会有一个交叉面&#xff0c;不过总的来说&#xff0c;技术面基本就是考察你的专业技术水平的&#xff0c;hr面的话主要是看这个人的综合素质以及家庭情况符不符合公司要求&#xff0c;一般来…...

分类预测 | MATLAB实现WOA-CNN-LSTM鲸鱼算法优化卷积长短期记忆网络数据分类预测

分类预测 | MATLAB实现WOA-CNN-LSTM鲸鱼算法优化卷积长短期记忆网络数据分类预测 目录分类预测 | MATLAB实现WOA-CNN-LSTM鲸鱼算法优化卷积长短期记忆网络数据分类预测分类效果基本描述模型描述程序设计参考资料分类效果 基本描述 1.Matlab实现WOA-CNN-LSTM多特征分类预测&…...

自然语言处理(NLP)之近似训练法:负采样与层序Softmax

我们在前面介绍的跳字模型与连续词袋模型有个缺陷就是在计算梯度时的开销随着词典增大会变得很大&#xff0c;因为每一步的梯度计算都包含词典大小数目的项的累加。为了降低这种带来的计算复杂度&#xff0c;介绍两种近似的处理方案&#xff1a;负采样和层序softmax负采样(Nega…...

关于上位机,C#

TCP与modbusTCP的区别 (10条消息) C#高级--常用数据结构_李宥小哥的博客-CSDN博客_c# 数据结构 C#中常用的数据结构 TCP/IP协议是网络通讯协议。MODBUS是应用与工业现场&#xff08;电子控制&#xff09;的通讯协议。两者的应用范围和应用环境有…...

华为OD机试真题 用 C++ 实现 - 字符串加密 | 多看题,提高通过率

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...