🚧 不知道“动态”体现在哪的动态规划
Kotori Y 27 Posts

动态规划(英语:Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题,并且记录所有子问题的结果,因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归,自底向上就是递推。

使用动态规划解决的问题有个明显的特点,一旦一个子问题的求解得到结果,以后的计算过程就不会修改它,这样的特点叫做无后效性,求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次,具有天然剪枝的功能,从而减少计算量。

以上是一段对动态规划不知所云的描述,我第一次看到的时候,一度怀疑这是否是人类所写下的语句。DP无论是在IO还是各大招聘中都是举足轻重的,虽然这些和我毫不相关,但锻炼一下思维肯定不是一件坏事。

0. DP

动态规划简单说就是将一个大问题拆分成若干小问题,并通过重复调用这些小问题中获得的结果得到最后的答案。例如入门的爬楼梯问题:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

对于上述问题,如果为1时,显然只有1种解法,为2时,显然也只有2种解法。当为3时,你可能不能立马得出答案为3。但不难发现,只需要分别在第一阶和第二阶的时候分别向上爬2和1阶就可以达到第三阶,也就是, 将这个公式推广开就可以得到:

即我们只需要记住前两个“台阶”的结果,即可得到当前台阶的结果。

1
2
3
4
5
6
7
8
9
10
11
12
const solution = (n) => {
let prev = 0, curr = 1
if (n===1) {
return 1
}

for (let i=0; i<n-1; i++) {
[curr, prev] = [curr+prev, curr];
}

return curr
}

复杂度为

  • Post title:🚧 不知道“动态”体现在哪的动态规划
  • Post author:Kotori Y
  • Create time:2021-05-06 08:42
  • Post link:https://blog.iamkotori.com/2021/05/06/不知道动态体现在哪的动态规划的笔记/
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments