本文实例讲述了JavaScript程序设计高级算法之动态规划。分享给大家供大家参考，具体如下：
主要是看了《数据结构与算法》有所感悟，虽然这本书被挺多人诟病的，说这有漏洞那有漏洞，但并不妨碍我们从中学习知识。
其实像在我们前端的开发中，用到的高级算法并不多，大部分情况if语句，for语句，swith语句等等，就可以解决了。稍微复杂的，可能会想到用递归去的解决。
但要注意的是递归写起来简洁，但实际上执行的效率并不高。
我们再看看动态规划的算法：
动态规划解决方案从底部开始解决问题， 将所有小问题解决掉， 然后合并成一个整体解决方案， 从而解决掉整个大问题 。
实例举例 （计算斐波那契数列）
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........
这个数列从第3项开始，每一项都等于前两项之和。
针对这个数列，可以用一个递归的函数去计算第n项 数值
// 斐波那契数列
function recurFib(n) {
if(n < 2){
return n ;
}else {
// document.write("第"+(n-1)+"次计算 n-1="+(n-1)+recurFib(n-1)+' ');
// document.write("n-2="+(n-2)+recurFib(n-2)+"<br>");
return recurFib(n-1)+recurFib(n-2)
}
}
确实是个非常简洁的代码，上面有被注释的代码 ，是用来打印出当n=多少，要执行多少次函数，不过明眼人一眼就能看出来执行的次数随着n的变大，次数也会非常恐怖增长。
当n=5的时候，递归树已经长的很大了……可以预见当n=10，甚至n=100的时候……
明白了递归函数执行效率之差，我们再来看的动态规划是如何做的
function dynFib(n) {
let val = [];
for(let i = 0; i <= n; ++i){
val[i]=0;
}
if(n ===1 || n === 2){
return 1;
}
else {
val[1] =1;
val[2] = 2;
for(let i = 3; i <= n; ++i){
val[i] = val [i-1] +val[i-2] ;
}
}
return val[n-1]
}
通过数组 val 中保存了中间结果， 如果要计算的斐波那契数是 1 或者 2， 那么 if 语句会返回 1。 否则，数值 1 和 2 将被保存在 val 数组中 1 和 2 的位置。
循环将会从 3 到输入的参数之间进行遍历， 将数组的每个元素赋值为前两个元素之和， 循环结束， 数组的最后一个元素值即为最终计算得到的斐波那契数值， 这个数值也将作为函数的返回值。
接下来可以写个简单的测试函数，来对比两者的运行时间。
// 定义一个测试函数，将待测函数作为参数传入
function test(func,n){
let start = new Date().getTime();//起始时间
let res = func(n);//执行待测函数
document.write('<br>'+'当n='+n+'的时候 '+res+'<br>');
let end = new Date().getTime();//结束时间
return (end - start)+"ms";//返回函数执行需要时间
}
打印函数执行
let time = test(recurFib,40); document.write(time); let time2 = test(dynFib,40); document.write(time2);
结果如下：
最后， 你或许已经意识到在使用迭代的方案计算斐波那契数列时， 是可以不使用数组的。
需要用到数组的原因是因为动态规划算法通常需要将中间结果保存起来。
以下是迭代版本的斐波那契函数义
function iterFib(n) {
let last = 1;
let nextLast = 1;
let result = 1;
for (let i = 2; i < n; ++i) {
result = last + nextLast;
nextLast = last;
last = result;
}
return result;
}
当然这个迭代版本的与数组的版本的效率也是相同的。
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。