动态规划入门（DAY-1）

Q1. 斐波那契数

题目描述：该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

由题可知，斐波那契数列的边界条件是和，每一项的和都等于前两项的和，递推关系为。

解法1 递归

def fibo(n):
    if n==0 or n==1:
         return n 
    return (fibo(n-1)+fibo(n-2))

解法2 动态规划

滚动数据思想，如下图所示[图显示不出来了]

def fibo(n):
    if n<2:
        return n
    p, q, r = 0, 1, 0  # 这里是初始化数组，p、q为初始0,1值，r是计算结果
    for i in range(2, n + 1):   # 循环条件为 从2开始
        r = p + q    # 计算条件
        p, q = q, r  # 数组滚动
    return r

心得：这道题十个月前做过，但是还是只会递归的方法，关于动态规划的思路，有点不清晰。

Q2 第 N 个泰波那契数

题目描述 泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

由题可知，斐波那契数列的边界条件是,和，每一项的和都等于前三项的和，递推关系为。

解法：动态规划

def fibo(n):
    if n==0:
        return 0
    if n==1 or n==2:
        return 1

    p, q, r, s = 0, 1, 1, 0  # 这里是初始化数组，p、q为初始0,1值，r是计算结果`  
    for i in range(2, n + 1):   # 循环条件为 从2开始`  
        r = p + q + s    # 计算条件`
        p, q, r = q, r, s  # 数组滚动` 
    return r`

**心得**：和Q1一模一样，加强记忆了，这种数组感觉像队列，依次出队列的感觉，也像滑动窗口，依次滚动的感觉。