您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > javascript

清晰明了的JavaScript版动态规划

时间:2019-12-23 10:29:07  来源:  作者:

算法是一种艺术,给人感觉很不好接近,但是一旦你和ta熟络了,你就能发现这门艺术的内在是多么美妙且多变。

对于前端来说,算法也许不是最重要的,在日常工作中,几乎很少用到。所以很多人也不是很感冒。

不过呢,有句话这么说的:面试造火箭,上班拧螺丝。咱们得先学习造火箭,才能有拧螺丝的机会。

莫得办法,既然想要拧螺丝,就要有好活的老学到老的觉悟。否则连改锥都没了。

那么,看题。

给你一个表格,像这样的:

清晰明了的JavaScript版动态规划

 

从 (0, 0) 到 (M, N)移动,并假设,每次只能向下或者向右移动一步,那么,请问一共有多少种不同的路径。

乍一看,好像可以遍历,依次向下或者向右找 (i + 1, j) 或者 (i, j + 1), 直至 (N, M)

比如下面这个简单版本:

清晰明了的JavaScript版动态规划

 

有六种路径:

清晰明了的JavaScript版动态规划

 

整理一下,相当于:

从(0, 0)开始,因为我们只能向下或者向右,所以我们先选择一条路去走,比如向右,这时候我们就走到了(1, 0)

清晰明了的JavaScript版动态规划

 

打叉的部分不代表不能走,只是代表当前流程下,我们只能选其一,也就是右

然后我们在(1, 0),继续走,可以向右或者向下,我们依然选择向右,这时候我们走到了(2, 0)

清晰明了的JavaScript版动态规划

 

然后再往下走,直至走到(N, M),

然后(1, 0),选择另外一条路,因为这仅仅是个 3*3 的表格,所以我们只能向下

清晰明了的JavaScript版动态规划

 

然后继续选择一个方向走直至(M, N)。

如此往复。

这样的话,其实可以转换成一个递归,也就是从(i, j) => (i + 1, j) | (i, j + 1),然后从(i + 1, j) => (x, y) 这样的一个递归方程式,不过这样性能是很差的,而且表格一旦规模变大,就会爆栈。

那么,我们如何有效的解决这个问题呢?

动态规划

ok,我们再次观察这个表格,我们其实会发现一个规律,就是套娃。

没错,表格把表格套娃了。

清晰明了的JavaScript版动态规划

 

这样一来,参考俄罗斯套娃,每个娃娃其实都是一样的,也就是本质一样,只不过体量逐渐变大,并且最小的那个娃娃不能继续套娃,也就是最小的那个娃娃就是起点。

如此一来,我们姑且可以用俄罗斯套娃来翻译一下这套题。

问:N个俄罗斯套娃合体后的总重量是多少?

答:由于最小的一个套娃无法继续套,并且可以得知这个套娃的重量,所以:

有二个套娃的时候,重量是最小的加上第二个

有三个套娃的时候,重量是两个套娃的重量的加上第三个

有四个套娃的时候,重量是三个套娃的重量的加上第四个

.

.

.

.

有N个套娃的时候,重量是(N - 1)个套娃的重量加上第N个

由此,我们可以得到一个式子:

dp(i) = dp(i - 1) + dp(i)

有没有感觉和表格题有些许类似?

我们可以任意 N * M 的右下角作为结束点,每一个都是一个套娃的角色,可能在当前环中是大套娃,但是到了下一环就成了小套娃,所以这个表格其实就是升级版的套娃。

清晰明了的JavaScript版动态规划

 

聪明的你,是不是发现了这个升级点在哪?没错,就是一次从(1, 1)开始,每次都是套两个娃,也就是理当前结束点最近的两个娃 => (1, 0) 和 (0, 1)

这样一来我们的公式自然而然就出来了,就是:

dp(N, M) = dp(N - 1, M) + dp(N, M - 1)

七点就是当N或者M为0的时候,也就是这个表格为一条直线,所以总路径都是1

这样我们的代码也就很容易写出来了,并且效率提升,不会有爆栈的问题,还做了之前的缓存。

function taowa(table) {    for (let yLen = table.length, y = yLen - 1; y >= 0; y--) {        for (            let xLen = table[0].length, x = xLen - 1;            x >= 0;            x--        ) {            if (x == xLen - 1 || y == yLen - 1) {                table[y][x] = 1;            } else {                table[y][x] = table[y + 1][x] + table[y][x + 1];            }        }    }    return table[y][x];}

举个例子: 4 * 5的表格有多少种路径?

清晰明了的JavaScript版动态规划

 

答: 35种

后续看到这,聪明的你会觉得,这个也太简单了吧,没错,算法就是这样。

难者不会,会者不难。

然后如果稍稍加点改造,可能又会花很长时间去这种类似 套娃 的规律,因为每种套娃的方式都不一样。

比如,还是这样表格,不求不同所有路径数量,将每个cell换成一个数字,求左上角到右下角的经过路径的路径内数字相加的最小值。也就是求最优解。

如下图:

清晰明了的JavaScript版动态规划

 

这道题的代码是什么呢?初学动态规划的朋友们可以一起讨论讨论

最后,简单总结下。

问题总是变幻莫测,只要你能找到其中的规律,一定能找到对应的解法。

对于动态规划这类问题,有几个特点:

  1. 有重复子问题(套娃)
  2. 单项(左上 => 右下)
  3. 分析作图后,结果类似二叉树


Tags:JavaScript   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1、通过条件判断给变量赋值布尔值的正确姿势// badif (a === 'a') { b = true} else { b = false}// goodb = a === 'a'2、在if中判断数组长度不为零...【详细内容】
2021-12-24  Tags: JavaScript  点击:(6)  评论:(0)  加入收藏
给新手朋友分享我收藏的前端必备javascript已经写好的封装好的方法函数,直接可用。方法函数总计:41个;以下给大家介绍有35个,需要整体文档的朋友私信我,1、输入一个值,将其返回数...【详细内容】
2021-12-15  Tags: JavaScript  点击:(20)  评论:(0)  加入收藏
作者:一川来源:前端万有引力 1 写在前面Javascript中的apply、call、bind方法是前端代码开发中相当重要的概念,并且与this的指向密切相关。本篇文章我们将深入探讨这个关键词的...【详细内容】
2021-12-06  Tags: JavaScript  点击:(19)  评论:(0)  加入收藏
概述DOM全称Document Object Model,即文档对象模型。是HTML和XML文档的编程接口,DOM将文档(HTML或XML)描绘成一个多节点构成的结构。使用JavaScript可以改变文档的结构、样式和...【详细内容】
2021-11-16  Tags: JavaScript  点击:(35)  评论:(0)  加入收藏
一、判断是否IE浏览器(支持判断IE11与edge)function IEVersion() {var userAgent = navigator.userAgent; //取得浏览器的userAgent字符串var isIE = userAgent.indexOf("comp...【详细内容】
2021-11-02  Tags: JavaScript  点击:(40)  评论:(0)  加入收藏
Null、Undefined、空检查普通写法: if (username1 !== null || username1 !== undefined || username1 !== '') { let username = username1; }优化后...【详细内容】
2021-10-28  Tags: JavaScript  点击:(51)  评论:(0)  加入收藏
1、前言async函数,也就是我们常说的async/await,是在ES2017(ES8)引入的新特性,主要目的是为了简化使用基于Promise的API时所需的语法。async和await关键字让我们可以用一种更简...【详细内容】
2021-09-17  Tags: JavaScript  点击:(61)  评论:(0)  加入收藏
为什么要使用 debugger这篇文章将介绍如何使用断点来进行 JavaScript 调试。在读这篇文章之前,需要问一个问题:为什么要使用断点来进行调试?我们首先需要认可使用断点的是必要...【详细内容】
2021-08-26  Tags: JavaScript  点击:(66)  评论:(0)  加入收藏
JavaScript 可以做很多好玩的事, 从复杂的框架到处理API,有太多的东西需要学习。但是,它也能让我们只用一行就能做一些了不起的事情。1. 获得一个随机的布尔值(true/false)该函数...【详细内容】
2021-08-19  Tags: JavaScript  点击:(77)  评论:(0)  加入收藏
JavaScript 提供了大量不同的处理数组的方法,这里花几分钟时间介绍 8 个项目中可以用到的数组方法。1. Array.map()使用.map() 方法,可以创建一个基于原始数组的修订版数组。....【详细内容】
2021-08-19  Tags: JavaScript  点击:(95)  评论:(0)  加入收藏
▌简易百科推荐
1、通过条件判断给变量赋值布尔值的正确姿势// badif (a === 'a') { b = true} else { b = false}// goodb = a === 'a'2、在if中判断数组长度不为零...【详细内容】
2021-12-24  Mason程    Tags:JavaScript   点击:(6)  评论:(0)  加入收藏
给新手朋友分享我收藏的前端必备javascript已经写好的封装好的方法函数,直接可用。方法函数总计:41个;以下给大家介绍有35个,需要整体文档的朋友私信我,1、输入一个值,将其返回数...【详细内容】
2021-12-15  未来讲IT    Tags:JavaScript   点击:(20)  评论:(0)  加入收藏
1. 检测一个对象是不是纯对象,检测数据类型// 检测数据类型的方法封装(function () { var getProto = Object.getPrototypeOf; // 获取实列的原型对象。 var class2type =...【详细内容】
2021-12-08  前端明明    Tags:js   点击:(23)  评论:(0)  加入收藏
作者:一川来源:前端万有引力 1 写在前面Javascript中的apply、call、bind方法是前端代码开发中相当重要的概念,并且与this的指向密切相关。本篇文章我们将深入探讨这个关键词的...【详细内容】
2021-12-06  Nodejs开发    Tags:Javascript   点击:(19)  评论:(0)  加入收藏
概述DOM全称Document Object Model,即文档对象模型。是HTML和XML文档的编程接口,DOM将文档(HTML或XML)描绘成一个多节点构成的结构。使用JavaScript可以改变文档的结构、样式和...【详细内容】
2021-11-16  海人为记    Tags:DOM模型   点击:(35)  评论:(0)  加入收藏
入口函数 /*js加载完成事件*/ window.onload=function(){ console.log("页面和资源完全加载完毕"); } /*jQuery的ready函数*/ $(document).ready(function(){ co...【详细内容】
2021-11-12  codercyh的开发日记    Tags:jQuery   点击:(36)  评论:(0)  加入收藏
一、判断是否IE浏览器(支持判断IE11与edge)function IEVersion() {var userAgent = navigator.userAgent; //取得浏览器的userAgent字符串var isIE = userAgent.indexOf("comp...【详细内容】
2021-11-02  V面包V    Tags:Javascript   点击:(40)  评论:(0)  加入收藏
Null、Undefined、空检查普通写法: if (username1 !== null || username1 !== undefined || username1 !== '') { let username = username1; }优化后...【详细内容】
2021-10-28  前端掘金    Tags:JavaScript   点击:(51)  评论:(0)  加入收藏
今天我们将尝试下花 1 分钟的时间简单地了解下什么是 JS 代理对象(proxies)?我们可以这样理解,JS 代理就相当于在对象的外层加了一层拦截,在拦截方法里我们可以自定义一些个性化...【详细内容】
2021-10-18  前端达人    Tags:JS   点击:(51)  评论:(0)  加入收藏
带有多个条件的 if 语句把多个值放在一个数组中,然后调用数组的 includes 方法。// bad if (x === "abc" || x === "def" || x === "ghi" || x === "jkl") { //logic } // be...【详细内容】
2021-09-27  羲和时代    Tags:JS   点击:(58)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条