10-I 裴波那契数列,动态规划

10-I 裴波那契数列

image.png
首先,纯递归需要大量重复的递归计算,超时。X

思路一:

新建一个长度为n的数组,用于在递归时存储arr(0)至arr(n)的数值。

摘自不死神兔_黑马程序员
image.png
注意:
新建的数组为n,则最后返回的值是arr[n-1]
新建的数组为n+1,则最后返回的值是arr[n]

操作:

image.png

思路二:

动态规划
一直变动的就是3个数,两个和数,一个为前一个数,一个为和
image.png

所求的第n个数,就是计算了第i次的a值

操作:

image.png

补充知识:

image.png
image.png
即,对因子取模后再取模和对最终结果取模的效果是一样的。

题目中有个用1000000007取模,如果数字越界就取模%1000000007,对1e9+7范围内的数取模也是本身,没有影响,但是100000008取模后就等于1。

评论

暂无评论