一、动态规划算法理论理解
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)
或者不用列表存储
或者使用递归