【ALGO】谈一谈动态规划

不得不说，光“动态规划”这四个大字看起来就很忽悠

当然这篇文章并不能准确详尽专业的对这四个大字进行阐述，只是聊聊我自己的理解，以及给出几个🌰，方便能更好的应用到刷题，呸，工作中…

基本思想

首先来说一下他的基本思想：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，再构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题求解。

参考过的文章也挺多，其中影响比较大的还是这篇来自逼知乎的回答：如何理解动态规划？ - zhen tan的回答 - 知乎

根据上面文章作者的描述，动态规划说白了就是高中数列题的魔改版。看起来确实像那么回事

设计步骤

若要用动态规划解决问题，以下三个步骤必不可少：

1. 建立状态转移方程（就是找规律，抽象成函数）
2. 缓存并复用以往结果（就是找到规律后把每一次的计算都存下来，后面使用的时候直接用）
3. 按顺序从小往大算

动态规划的特点

• 把原始问题划分成一系列子问题
• 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接读取，不重复计算
• 自底向上的计算
• 整体问题的最优解取决于子问题的最优解（也就是状态转移方程的好坏）（将子问题称之为状态，最终状态的求解归结为其他状态的求解）

几个例子🌰

最简单的爬楼梯问题

有一段连续的楼梯，共100阶台阶。明强的腿比较短，他最多一次迈两阶台阶，要从楼梯底部向上爬到楼梯顶部。问他一共有多少种走法？

这个问题乍一看好像很复杂，但是你再乍一下，用上动态规划，他就很清晰了。我们来问这么几个问题：

1. 他上到第1节台阶有几种走法？显然是只有1种
2. 他上到第2节台阶有几种走法？显然有1+1、0+2，也就是2种
3. 他上到第3节台阶有几中走法？显然有1+1+1、1+2、2+1，也就是3种
4. 他上到第4节台阶有几中走法？显然有1+1+1+1、1+1+2、1+2+1、2+1+1、2+2，也就是5种
   也就是说f(1)的最优解是1，f(2)的最优解是2，f(3)的最优解是3，f(4)的最优解是5，看到规律了吗，这™️显然就是一个斐波那契数列呀。但是为什么呢？我来解释一下：

试问：
你想一次就上到第3节台阶的话，你前一步只能在那几个台阶上？显然你只能在第1节或者第2节上
同理，你想一次就上到第4节台阶的话，你前一步只能在那几个台阶上？显然你只能在第2节或者第3节上，为什么不能在第1节上呢，因为一次迈3节容易扯着🥚…

所以就出来了，你上到第n节的台阶的最优解就是 你上到n-1节的最优解 + 你上到n-2节的最优解。

这个问题你当然可以用递归来解，但是用递归的时间复杂度已经是指数级的了，下面是用动态规划思想写的代码，没有经过优化，方便理解：

1
2
3
4
5
6
7
8
9
10
11

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

时间复杂度瞬间降到了O(n)，但是这样会有一个问题，就是后面的数据太大，导致我在刷这道题👇的时候总是出不来正确结果：

剑指 Offer 10- I. 斐波那契数列

我的代码是最后一步才做取模运算，殊不知，在往数组里存的时候就要存成取模的结果。无语😓

今晚上已经很累了，后面想到其他的再更新吧。