透过"斐波那契数列"，初探动态规划

今天暂时先不介绍Monaco（二），留着端午节给大家放大招～～～

步入正题，斐波那契数列，想必大家都耳熟能详：

1
2

F(n) = F(n-1) + F(n-2)     (n>1)

下面开始coding时刻：

递归版本

1
2
3
4
5
6
7
8
9

/**
 * @desc 简单、粗暴、但又不缺乏美感，nice
 * @param n
 * @returns {*}
 */

const fib = n => n > 1 ? fib(n-1) + fib(n-2) : n;

但是缺点很明显，会进行很多重复的计算。

接下来抛砖引玉～

动态规划方法安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此动态规划算法是付出额外的内存空间来节省计算时间，是典型的时空权衡的例子。

上述解释来源: https://www.zhihu.com/question/24347044

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const memoRes = {
    0: 0,
    1: 1
}
const fib = n => {

    for(let i = 2; i<=n&&n>=2; i++) {
        memoRes[i] = memoRes[i-1] + memoRes[i-2] % 1000000007;
        if(i>3) {
            delete memoRes[i-2];
        }
    }

    return memoRes[n]
}

这大概就是传说中的空间换时间，一次 for 循环记录完所有的结果，返回最终需要的结果；

这里解释下，为什么每次都要 delete memoRes[i-2]，因为本次用完之后可以最快释放内存，下次顶多用到i-1,但是需要注意i必须大于3;

需要再解释下：为什么要对求和结果取模 1000000007

知乎传送门: https://www.zhihu.com/question/49374703

这里引用一段比较直观的回答：

b乎莫名其妙给我推荐了一番，那我就来解释一番1e9+7这个数，满足[0,1e9+7)内所有数，两个数相加不爆int，两个数相乘不爆long long还有一点，由于1e9+7是质数，所以在[1,1e9+7)内所有数都存在关于1e9+7的逆元（这样就可以做除法）至于998244353，是个质数并且可以表示成a2^b+1的形式，其中b大概为20多（？），假设我们有一个原根g使得g^0,g^1,…,g^998244351取得所有[1,998244353)的数，由于b中有很多2的因子，这样g^n可以代替单位根 ；由于fft需要下标为2的幂次的单位根，这样代替使得n取得整数；从而进行数论上的fft(ntt)操作，这种数字一般会提示你这题要用ntt，类似的数字还有1004535809然后vfk就说以后所有要取模的题就都写998244353就好了（来迷惑选手），这个数也被称为uoj素数。（其实不满足这种a2^b+1的也可以，参见任意模数NTT然后这些数字由于很常用（包括某人的生日19****17），经常被毒瘤出题人卡哈希，写哈希慎用

LeetCode是完美通过的～

大概做一下小结，透过一道简单的算法题目，简要理解一下”动态规划”的初级奥义，后续会继续跟进相关题目做题解～～～