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

本文主要是介绍动态规划算法学习（一）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 斐波那契数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程