动态规划-斐波那契数列模型

在几个月前我就在尝试学习动态规划，但是由于我的智力有限始终不懂。一直认为动态规划是记忆化搜索的进阶。如今我重新开始学习动态规划，该文章是笔记。

由于斐波那契数列模型我只写一篇文章，下面的题目我都不会讲解，但是写完这些题，让我受益匪浅。

1. 第 N 个泰波那契数

class Solution {
public:
    int tribonacci(int n) {
        if(n==0)return 0;
        if(n==1||n==2)return 1;
        vector<int> res(n+1,0);
        res[1]=res[2]=1;
        for(int i=3;i<=n;++i)
        {
            res[i]=res[i-1]+res[i-2]+res[i-3];
        }
        return res[n];
    }
};

2.三步问题

const int MX=1000000,MOD=1000000007;
vector<long long> f(MX+1,0);
//这题相当于填空题，答案是固定的，所以我们可以只完成一次后面再直接返回答案
int init=[](){
    f[0]=1,f[1]=1;
    f[2]=2,f[3]=4;
    for(int i=3;i<=MX;++i){
        f[i]=(f[i-1]+f[i-2]+f[i-3])%MOD;
    }
    return 0;
}();
 
class Solution {
public:
    int waysToStep(int n) {
        return f[n];
    }
};

3.解码方法

class Solution {
public:
    int numDecodings(string s) {
        if(s[0]=='0')return 0;
        int n=s.size();
        int a=0,b=0,c=0;
        a=1,b=s[0]!='0';
        for(int i=2;i<=n;++i){
            if(s[i-1]!='0')c+=b;
            int t=(s[i-2]-'0')*10+s[i-1]-'0';
            if(t>=10&&t<=26)c+=a;
 
            a=b,b=c,c=0;
        }
        return b;
    }
};

斐波那契额数列模型：

个人认为：全部都是爬楼梯的变形，前两题不做叙述， 解码方法这题的思路也是爬楼梯的衍生：

一位数决定一个字母，两位数依然决定一个字母：相当于:dp[i]=dp[i-1]+dp[i-2]。剩余的就是判断边界条件，当个位为0时表面dp[i]不能接收dp[i-1]，这也表明了当两位数小于10或者大于26也不能接收dp[i-2]。

结尾：所有的斐波那契数列都是dp[i]=dp[i-1]+dp[i-2]