JavaScript网格中的最小路径讲解
目录
- 问题描述
- 思路分析
- AC代码
问题描述
给你一个下标从 0 开始的整数矩阵 grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ，且满足 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一个单元格。注意： 在最后一行中的单元格不能触发移动。
每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。
grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。
示例 1：
输入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]] 输出：17 解释：最小代价的路径是 5 -> 0 -> 1 。 - 路径途经单元格值之和 5 + 0 + 1 = 6 。 - 从 5 移动到 0 的代价为 3 。 - 从 0 移动到 1 的代价为 8 。 路径总代价为 6 + 3 + 8 = 17 。
示例 2：
输入：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]] 输出：6 解释： 最小代价的路径是 2 -> 3 。 - 路径途经单元格值之和 2 + 3 = 5 。 - 从 2 移动到 3 的代价为 1 。 路径总代价为 5 + 1 = 6 。
提示：
m == grid.length n == grid[i].length 2 <= m, n <= 50 grid 由从 0 到 m * n - 1 的不同整数组成 moveCost.length == m * n moveCost[i].length == n 1 <= moveCost[i][j] <= 100
思路分析
这道题目其实并不难，难的是对于题目的理解，题目有点长和绕，我们需要仔细阅读清楚题目给的信息，结合示例一的图片进行理解会更清晰。
1、题目会给出一个 m * n 的矩阵；
一个下标从 0 开始的整数矩阵 grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成。
2、每一行的格子可以移动到下一行的任意一格；
在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ，且满足 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一个单元格。
3、moveCost[i][j]表示从值为 i 的单元格移动到下一行第 j 列单元格的代价
每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。
4、求从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。
grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。
理清楚上面的这四个信息之后，我们可以发现这是一道经典的dp动态规划的题目,我们每一个格子的上一步只能是上一行的某一格，我们只需要自顶向下求出移动到每一个格子的最下代价即可。
遍历矩阵的每一个格子，维护上一行到当前格子的最小代价，最后求出最后一行的格子的最小代价即可。
AC代码
/**
* @param {number[][]} grid
* @param {number[][]} moveCost
* @return {number}
*/
var minPathCost = function(grid, moveCost) {
let dp = new Array(grid.length);
let res = Infinity;
for(let i = 0; i < dp.length; i++){
dp[i] = new Array(grid[i].length).fill(0);
for(let j = 0; j < dp[i].length; j++){
if(i === 0) dp[i][j] = grid[i][j];
else{
let temp = Infinity;
for(let k = 0; k < dp[i].length; k++){
temp = Math.min(temp,dp[i - 1][k] + moveCost[grid[i - 1][k]][j]);
}
dp[i][j] = temp + grid[i][j];
}
if(i == grid.length - 1){
res = Math.min(dp[i][j],res);
}
}
}
return res;
};
到此这篇关于JavaScript网格中的最小路径讲解的文章就介绍到这了,更多相关JS网格内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
原生JS实现图片网格式渐显、渐隐效果
先给出效果图: 写的小组件支持图片的渐显.渐隐,并且可以是有序.随机两种方式. 我采用的原型是属性写在构造函数内,方法写在原型对象内.方法写构造函数内有个问题,就是每次调用这个方法就相当于重新实例化一次,举个粟子: 实现网格效果的原理上是将读取图片的宽高,按照设定的参数,分成等高宽的网格(我用的span标签表示的网格),网格利用定位铺满整个图片,每个网格的背景图都是原图片,原理同sprite,利用background-position属性改变显示区域.接下来就是按照设定的顺序实现渐显或渐隐.渐显
-
分享十三个最佳JavaScript数据网格库
JavaScript 是一种通常被用在网页开发中的编程语言.它主要是在互联网上的网页浏览器中开发出效果出众且可交互的特效.它是客户端脚本语言中的一种,是被用来作为通过用户的网页浏览器进行处理的源代码.JavaScript 是动态.高级.可解释且无类型的编程语言.JavaScript 主要被用在不是基于 Web 的环境之中,像是特定站点的浏览器,桌面小部件以及 PDF 文件.事实上,JavaScript 还被程序员们用在了视频游戏开发之中. 数据网格可以帮助解决在 HTML 表格上对带有过滤.分页
-
Javascript Bootstrap的网格系统,导航栏和轮播详解
目录 bootstrap简介及其相关内容 网格系统 列嵌套 列偏移 列排序 导航栏 轮播 总结 bootstrap简介及其相关内容 Bootstrap 是一个用于快速开发 Web 应用程序和网站的前端框架.引用其时需要具备一定的基本模板: <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name=&q
-
Vue.js实现网格列表布局转换方法
实现效果: 实现代码及注释: <!DOCTYPE html> <html> <head> <title>布局转换</title> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta http-equiv=&quo
-
JavaScript Canvas绘制六边形网格
本文实例为大家分享了JavaScript Canvas绘制六边形网格的具体代码,供大家参考,具体内容如下 使用Canvas绘制六边形网格. 主要思路是先画给定中心点的六边形,然后二重循环遍历所有中心点,画所有的六边形. <!DOCTYPE HTML> <html> <body> <canvas id="myCanvas" width="300" height="150"> <p>
-
Three.js中网格对象MESH的属性与方法详解
前言 本文主要给大家介绍了关于Three.js网格对象MESH的属性与方法,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍: 创建一个网格需要一个几何体,以及一个或多个材质.当网格创建好之后,我们就可以将它添加到场景中并进行渲染.网格对象提供了几个属性和方法用于改变它在场景中的位置和显示效果. 如下: 还有一个属性就是visible属性,默认为true,如果设置为false,THREE.Mesh将不渲染到场景中. mesh对象的前三个属性position,rotation和scal
-
Three.js学习之网格
前言 小编之前发布过关于几何形状和材质,相信大家看过学习之后,我们就能使用他们来创建物体了.最常用的一种物体就是网格(Mesh),网格是由顶点.边.面等组成的物体:其他物体包括线段(Line).骨骼(Bone).粒子系统(ParticleSystem)等.创建物体需要指定几何形状和材质,其中,几何形状决定了物体的顶点位置等信息,材质决定了物体的颜色.纹理等信息. 1.创建网格 在前几篇中,我们学习了如何创建几何形状与材质,而网格的创建非常简单,只要把几何形状与材质传入其构造函数.最常用的物体是网
-
JavaScript实现拖拽元素对齐到网格（每次移动固定距离）
这几天在做一个拖拽元素的附加功能,就是对齐到网格,实际上就是确定好元素的初始位置,然后拖拽元素时,每次移动固定的距离.让元素都可以在网格内对齐.先上效果图,然后在详细说明一下细节问题 做了一个gif图,可以看到,每次元素的移动都是按照最小单位距离移动的.且每次元素都是对齐到网格的. 先根据demo说明一下思路和细节,后面会给出demo代码. 1. 确定元素的每次移动的最小单位(demo中为10px和10px),也就是每次水平或垂直的位移量都是10px.铺上一层网格背景是为了帮助我们更好的看到效果
-
JavaScript网格中的最小路径讲解
目录 问题描述 思路分析 AC代码 问题描述 给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0 到 m * n - 1 的不同整数组成.你可以在此矩阵中,从一个单元格移动到 下一行 的任何其他单元格.如果你位于单元格 (x, y) ,且满足 x < m - 1 ,你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一个单元格.注意: 在最后一行中的单元格不能触发移动. 每次可能的移动都需要付出对应的代价,
-
JavaScript之创意时钟项目(实例讲解)
"时钟展示项目"说明文档(文档尾部附有相应代码) 一.最终效果展示: 二.项目亮点 1.代码结构清晰明了 2.可以实时动态显示当前时间与当前日期 3.界面简洁.美观.大方 4.提高浏览器兼容性 三.知识点汇总: jQuery.原生javascript.css3.h5 四.重难点解释 1.各个指针的旋转角度的获取 首先要明确如下概念: 时钟指针旋转一周360度 时针: 表盘上共有12小时,每经过一小时,要旋转30度: 分针: 表盘上共有60个小格子,分针每走一分钟,经过一个小格子,转动6
-
JavaScript实现简单的双色球(实例讲解)
如下所示: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>双色球</title> <link rel="stylesheet" type="text/css" href="css/twoToneClass.css" rel="e
-
深入理解JavaScript程序中内存泄漏
垃圾回收解放了我们,它让我们可将精力集中在应用程序逻辑(而不是内存管理)上.但是,垃圾收集并不神奇.了解它的工作原理,以及如何使它保留本应在很久以前释放的内存,就可以实现更快更可靠的应用程序.在本文中,学习一种定位 JavaScript 应用程序中内存泄漏的系统方法.几种常见的泄漏模式,以及解决这些泄漏的适当方法. 一.简介 当处理 JavaScript 这样的脚本语言时,很容易忘记每个对象.类.字符串.数字和方法都需要分配和保留内存.语言和运行时的垃圾回收器隐藏了内存分配和释放的具体细节. 许
-
使用JavaScript为一张图片设置备选路径的方法
在做网页开发的时候,有时候希望给图片设置一个备选路径,即,当src属性对应的主路径加载失败的时候,图片可以马上切换到备选路径.这样,即使主路径失效了,显示备用路径也不会影响网页的正常体验. 注意到网页中一张图片加载失败会触发error事件,因此可以使用DOM模型中的load和error事件实现这一效果. src1='main/image.jpg' //主路径 src2='another/image.jpg' //备用路径 jQuery 1.8以前 使用load和error方法捕捉事件 $('#i
-
基于js中的原型(全面讲解)
在讲js的原型之前,必须先了解下Object和Function. Object和Function都作为JS的自带函数,Object继承自己,Funtion继承自己,Object和Function互相是继承对方,也就是说Object和Function都既是函数也是对象. console.log(Function instanceof Object); // true console.log(Object instanceof Function); // true Object 是 Function
-
jQuery中的AjaxSubmit使用讲解
最近在使用ajaxForm,随便把使用方法记下下来,以便以后回顾. 1 ,引入依赖脚本 <script type="text/javascript" src="/js/jquery/jquery.form.js"></script> //ajaxForm 依赖脚本 <script type="text/javascript" src="/js/jquery/jquery-1.8.0.min.js"
-
JavaScript函数中的this四种绑定形式
正文 javascript中的this和函数息息相关,所以今天,我就给大家详细地讲述一番:javascript函数中的this 一谈到this,很多让人晕晕乎乎的抽象概念就跑出来了,这里我就只说最核心的一点--函数中的this总指向调用它的对象,接下来的故事都将围绕这一点展开 (提醒前排的筒子们准备好茶水和西瓜,我要开始讲故事啦!!) [故事]有一个年轻人叫"迪斯"(this),有一天,迪斯不小心穿越到一个叫 "伽瓦斯克利"(javascript)的 异世界,此时此
-
Python图像处理之识别图像中的文字(实例讲解)
①安装PIL:pip install Pillow(之前的博客中有写过) ②安装pytesser3:pip install pytesser3 ③安装pytesseract:pip install pytesseract ④安装autopy3: 先安装wheel:pip install wheel 下载autopy3-0.51.1-cp36-cp36m-win_amd64.whl[点击打开链接] 执行命令:pip install E:\360安全浏览器下载\autopy3-0.51.1-cp36
-
详解Vue.js中引入图片路径的几种方式
vue --version 3.6.3 记录总结一下的Vue中引入图片路径的几种书写方式 vue中静态资源的引入机制 Vue.js关于静态资源的官方文档 静态资源可以通过两种方式进行处理: 在 JavaScript 被导入或在 template/CSS 中通过相对路径(以 . 开头)被引用.这类引用会被 webpack 处理. 诸如 <img src="..."> . background: url(...) 和 CSS @import 的资源 例如, url(./imag