动态规划算法学习(一)leetcode:509 斐波那契数

一、动态规划算法理论理解

1、动态规划算法的思想(概念):将带求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解中得到原问题的解。需要注意,适用于动态规划求解的问题,经分解的到的子问题往往不是相互独立的。

2、动态规划算法五部曲:

a.明确dp[i]数组的含义,i的含义

b.推导递推公式

c.初始化dp[i]数组

d.确定遍历顺序

e.打印dp[i]数组

二、算法题解

1、题:斐波那契数形成的序列称为斐波那契数列,该数列由0和1开始,后面的每一项数字都是前面两项数字的和,也就是:

F(0)=0,F(1)=1

F(n)=F(n-1)+F(n-2),其中n>1

给定n,请计算F(n)

2、思路:该题刚好符合动态规划思想,子问题的解可以得到原问题的解,并且不是相互独立的。

a.dp[i]表示F(i),即第i个斐波那契数是多少

b.递推公式:F(n)=F(n-1)+F(n-2)

c.数组初始化:dp[0]=0,dp[1]=1

d.遍历顺序从前往后

3.代码(Python3)

动态规划算法学习(一)leetcode:509 斐波那契数

或者不用列表存储

 动态规划算法学习(一)leetcode:509 斐波那契数

 或者使用递归

动态规划算法学习(一)leetcode:509 斐波那契数

 

上一篇:Flash AS 入门教程 圆和椭圆函数的应用


下一篇:最长公共子序列