跳到主要内容位置

算法:动态规划

动态规划是一种计算机编程方法,通过将一个大的问题,递归的分解成子问题,然后对每个子问题应用同样的解决方案,经过组合得到大问题的答案。 动态规划必须要满足两个特定的条件:

  • 重叠子问题
  • 最优子结构

重叠子问题指的是,子问题的答案,会在其他子问题中重复用到,动态规划会保存子问题的答案来避免重复计算。 最优子结构指的是给定的大问题的最优答案可以通过合并子问题的最答案来获得。

动态规划的解法

动态规划的解法有两种:

  • 自顶向下。
  • 自底向上。

自顶向下递归的从大问题开始,逐一计算子问题,并把子问题的结果保存起来,后面如果再用到相同子问题的结果,则直接从保存的结果中获取。 自底向上与自顶向下的方式相反,先从最小的子问题计算,同时也保存计算结果,直到计算到大问题本身,得到最终答案。

一个例子

这节课我们来看一个最简单的例子,计算斐波那契数列,如果使用递归的方式实现,需要重复计算很多次:

function fib(n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}

这样,即使指定 n 为一个较小的数字,也会需要很长的时间才能计算完成。 这个时候,如果我们通过一个数组,把之前计算的结果保存起来,这样就省去了所有的重复计算,直接拿前边两个计算结果进行相加就可以了:

function fib(n) {
const fib = [0, 1];
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}

算法执行效率会大大提高。 这样就利用到了动态规划,这个示例是自底向上的方式来解决的,即从 0 开始一直计算到 n,如果采用自顶向下则从 n 计算到 0,这里就不演示了。

不是所有的递归都可以用动态规划来解决

要注意的是,并不是所有的递归算法都能用动态规划来优化,例如归并排序,因为它的子问题没有重叠之处,对每个子数组都要进行排序,所以它的这种解法叫做分治,而不是动态规划。

动态规划适用的问题

动态规划可以解决有下面这些描述的问题:

  • 求最长公共子序列
  • 背包问题
  • 计算到达目的走法数量

小结

好了,这个就是动态规划的简介,你学会了吗?如果有帮助请三连并关注,想学更多的开发知识,可以在评论区留言,感谢观看!

提示

一系列的课程让你成为高级前端工程师。课程覆盖工作中所有常用的知识点和背后的使用逻辑,示例全部都为工作项目简化而来,学完即可直接上手开发!

即使你已经是高级前端工程师,在课程里也可能会发现新的知识点和技巧,让你的工作更加轻松!

《React 完全指南》课程,连载中现只需 48 元(领取优惠券)点击查看详情。

《Vue 3.x 全家桶完全指南与实战》课程,包括 Vue 3.x、TypeScript、Vue Router 4.x、Vuex 4.x 所有初级到高级的语法特性详解,让你完全胜任 Vue 前端开发的工作。点击查看详情。

《React即时通信UI实战》课程,利用 Storybook、Styled-components、React-Spring 打造属于自己的组件库。

《JavaScript 基础语法详解》本人所著图书,包含 JavaScript 全面的语法知识和新特性, 可在京东、当当、淘宝等各大电商购买