前言
最近又看到一篇文章, 说到算法对前端的重要性, 遂抽出时间(玩的时间), 逼着自己看一些相关的知识, 当看到动态规划相关文献时, 也勾起了很大的兴趣, 学习各位大神的博客, 有了初步理解, 借此记载, 可能比较浅显, 对于同样初学相关知识的同学, 或许会有帮助, 如有问题, 望大神指出
正文
学习的最好方法便是带着问题学习, 所以首先先采用网上普遍的、对理解动态规划很友好的一个问题作为学习切入点, 问题解决后再总结归纳
问题:
现在有 10 级台阶, 每次只能上 1 级或 2 级台阶, 问: 到达 10 级台阶的方法有多少?
解析:
首先按照正常逻辑, 看到这个问题或许会懵, 因为情况太多无从下手, 但是最优解往往需要更改思考方式
这里可以从结果考虑, 最后我们踩在第 10 级台阶上, 由于每次只能上 1 或 2 级台阶, 所以上一步, 我门应该在第 9 级台阶, 或第 8 级台阶;
基于 1 的结论, 从 0 到 9 级台阶有多少种方法, 对应的从 9 到 10 级台阶就有多少种方法 (这里需要理解下), 同理从 0 到 8 级台阶的方法总数等于从 8 到 10 级台阶的方法总数, 可得从 0 到 10 级台阶的方法总数(以下简称 methods(10)) 等于 从 0 到 9 级台阶的方法总数 加 从 0 到 8 级台阶的方法总数, 即 methods(10) = methods(9) + methods(8); 这里的 methods(9) 和 methods(8)就是 methods(10)的最优子结构(思维导图有点大, 只展示一部分)
从第 2 点我门已经发现了问题的解决逻辑和一点思路, 按照第 2 点的思路, 我们将以二叉树的形式将问题分裂成“无数”的子问题, 直到分裂成 methods(2) 和 methods(1)时,methods(2)(从 0 到 2 级台阶的方法数)等于 2, 而 methods(1)等于 1, 这里的 methods(2) 和 methods(1)也就是动态规划里边界
由 3 的结论, 我们只需要将所有子问题的解相加便是问题结果, 这里将思路转为代码, 通过递归实现, methods(n) = methods(n – 1) + methods(n – 2),methods(n – 1) = ……, 以此类推
function methods(n) {
if (n == 1) return 1
if (n == 2) return 2
console.log(‘ 计算 ’)
return methods(n – 1) + methods(n – 2)
}
console.log(methods(10)); // 89
问题到这看似已经解决了, 但是我想同学在思维导图中应该也发现了, 很多子问题是重复的, 但是上面代码却做了很多重复工作, 很浪费 冗余(如下图), 我们希望已经计算过的就不要在重复计算
所以优化下, 保存计算过的结果:
var resultList = [] // 保存计算过的结果, 以计算的台阶数做索引下标
function methods(n) {
if (n == 1) return 1
if (n == 2) return 2
if (!resultList[n]) {// 没有就保存
console.log(‘ 计算 ’, n)
resultList[n] = methods(n – 1) + methods(n – 2)
}
return resultList[num]
}
这样看, 就节省了很多计算, 台阶总数越大, 越明显然后咱们再精简下代码:
var resultList = [0, 1, 2]; // 对于本题的结果预存了, 方便点
function fnSumF(n) {
if (!resultList[n]) resultList[n] = fnSumF(n – 1) + fnSumF(n – 2);
return resultList[n]
}
总结
动态规划的英文名是 Dynamic Programming，是一种分阶段求解决策问题的数学思想; 与分治方法类似，都是通过组合子问题的解来来求解原问题的。再来了解一下什么是分治方法，以及这两者之间的差别，分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。而动态规划与之相反，动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治方法会做许多不必要的工作，他会反复求解那些公共子子问题。而动态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。
其实关于和分治的区别, 在我们解决问题优化时已经可以看出
初学的浅层理解, 如有问题希望大家指出, 指点, 如果问题或者好文章, 也希望可以评论推荐
学的越多, 才发现自己懂得越少