动态规划每日一练(1)

1.斐波那契

class Solution {
    
public:
    int fib(int n) {
    
        if(n<=1)
        {
    
            return n;
        }
        else{
    
            int q=0,p=0,s=1;
            for(int i=2;i<=n;++i)
            {
    
                q=p;
                p=s;
                s=p+q;
            }
             return s;
        }
       
    }
};

斐波那契数的边界条件是 F(0)=0F(0)=0 和 F(1)=1F(1)=1。当 n>1n>1 时，每一项的和都等于前两项的和，因此有如下递推关系：

F(n)=F(n-1)+F(n-2)
F(n)=F(n−1)+F(n−2)

2.T泰波那契序列

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

class Solution {
    
public:
    int tribonacci(int n) {
    
        if(n<=3)
        {
    
            if(n==0)
            {
    
                return 0;
            }
            else if(n<=2)
            {
    
                return 1;
            }
            else
            {
    
                return 2;
            }
        }
        else{
    
            int p=0,q=1,o=1,s=2;
            for(int i=4;i<=n;i++)
            {
    
                p=q;
                q=o;
                o=s;
                s=p+q+o;
            }
            return s;
        }
    }
};