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

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

六月 11, 2021 本文共计: 778 字 预计阅读时长: 3分钟

今天暂时先不介绍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是完美通过的~

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