【动态规划】斐波那契额数列模型

1. 前言

做动态规划的题目，题目有个固定的模式:

1. 状态表示； 先创建一个表，叫dp表。 状态表示就是：dp表里面存的那个值所表示的含义。

那么怎么确定状态表示呢？ （1）题目要求 （2）经验+题目要求 （3）分析问题过程中发现重复子问题

1. 状态转移方程； dp[i]等于什么？ 像这个就是一个状态转移方程：dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; 每一道题目的状态转移方程是不一样的。
2. 初始化； 初始化就是保证填表不越界。 根据状态转移来填表的时候，不能越界访问。
3. 填表顺序； 为了填写当前状态的时候，所需要的状态已经计算过了。
4. 确定返回值。 题目要求+状态表示

写代码的四大部分： 1.创建dp表 2.初始化 3.填表 4.确定返回值

2. 1137第 N 个泰波那契数

将题目给的条件Tn+3 = Tn + Tn+1 + Tn+2同时减去3，就能得到下面这个式子，也就是说第n个等于它前面三项之和。

2.1 分析

1.创建dp表 先根据题目要求先创建dp表,这里要包含n个数，就建一个n+1大小的dp表：vector<int> dp(n+1)

2.初始化 根据题目已给的定义初始化 dp[0]=0;dp[1]=dp[2]=1;

3.填表 在循环里面根据题目已给的公式写出循环 dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

4.确定返回值 最后返回得到的结果return dp[n];

处理边界问题: 这里考虑到可能会越界，就得先加一个判断：

if(n==0) return 0;
if(n==1||n==2) return 1;

这个代码空间复杂度为O(n)，优化一下代码，将空间复杂度降到O(1)。

写出几项就会发现，将设置的几个变量连续赋值，就能达到滚动的效果。将b的值先赋给a,在c的值先赋给b,d的值先赋给c。就这样一直到n，最后返回d的值就行。

2.2 代码

class Solution {
public:
    int tribonacci(int n) {
        
        if(n==0) return 0;
        if(n==1||n==2) return 1;
       vector<int> dp(n+1);

        dp[0]=0;
        dp[1]=dp[2]=1;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
};

优化空间后的代码:

class Solution {
public:
    int tribonacci(int n) {
        
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int a=0,b=1,c=1, d=0;
        for(int i=3;i<=n;i++)
        {
            d=a+b+c;
            a=b;
            b=c;
            c=d;
        }
        return d;      

    }
};

3. 面试题 08.01. 三步问题

3.1 分析

假设要到第4个台阶，就可以从第3个台阶到第4个台阶，也可以从第2个台阶到第4个台阶，还可以从第1个台阶到到第4个台阶，总的到第第4个台阶的方法也就是上面加的和。

1. 状态表示 以i位置为结尾 dp[i]表示：到达i位置时，一共有多少种方法
2. 状态转移方程； 以i位置的状态，最近的一步，来划分问题。 就有三种情况： （1）从i-1位置到i位置，正好是到达i-1位置时候一共的方法，就是dp[i-1]， （2）从i-2位置到i位置，正好是到达i-2位置时候一共的方法，就是dp[i-2]， （3）从i-3位置到i位置，正好是到达i-3位置时候一共的方法，就是dp[i-3]，

那么很显然，要到第i个台阶，知道到第i-1和i-2和i-3有多少种就可以了：

dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

1. 初始化； 填1,2，3位置上会出现越界，所以先初始化他们： dp[1]=1;dp[2]=2;dp[3]=4;
2. 填表顺序； 从左往右
3. 确定返回值 返回dp[n]

    if(n==1||n==2)return n;
    if(n==3)return 4;

题目还要求取模，就直接定义一个int const Mod=1e9+7;用来取模。 最后返回return dp[n];就行。

3.2 代码

编写代码： 1.创建dp表 2.初始化 3.填表 4.确定返回值

class Solution {
public:
    int waysToStep(int n) {
    int const Mod=1e9+7;
    if(n==1||n==2)return n;
    if(n==3)return 4;

     vector<int> dp(n+1);
     dp[1]=1;dp[2]=2;dp[3]=4;
     for(int i=4;i<=n;i++)
     {
        dp[i]=((dp[i-1]+dp[i-2])%Mod+dp[i-3])%Mod;
     }
     return dp[n];
    }
};

4. 746使用最小花费爬楼梯

楼顶在哪里? 题目所给的数组都是楼梯，当把楼梯都跨过去才是楼顶，也就是数组最后一个位置的下一个位置才是楼顶。

4.1 分析

这里得先明白到达楼梯顶部不是这里顺序表的长度，而是长度再加1。

4.1.1 以i位置为终点

1. 状态表示 以i位置为终点 dp[i]表示：到达i位置时的最小花费
2. 状态转移方程； 用之前或者之后的状态，推导出dp[i]的值

这里选择的是对应花费最小的那一个再加上它对应dp表所对应的值：

dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

1. 初始化； 在初始化的时候，题目已经给出可以下标为 0 或下标为 1 的台阶开始爬楼梯，那么他们对应的花费就为0：

dp[0]=dp[1]=0;

1. 填表顺序； 从左往右
2. 确定返回值 最后返回最小花费：

 return dp[n];

4.1.2 以i位置为起点

1. 状态表示 以i位置为起点 dp[i]表示：到达i位置时，到达楼顶，此时的最小花费。 以第i个台阶为起点，就得先到达第i+1或者第i+2个台阶，看一下到达哪个台阶对应的花费低，就到达哪一个台阶。

支付完i位置走到i+1位置，再到终点 支付完i位置走到i+2位置，再到终点

1. 状态转移方程；

状态转移方程就是：

dp[i]=min(dp[i+1],dp[i+2])+cost[i];

1. 初始化；

此时初始化的位置就是n-1和n-2：

     dp[n-1]=cost[n-1];
     dp[n-2]=cost[n-2];

1. 填表顺序； 从右往左
2. 确定返回值 最后返回的结果是0和1位置的最小值：

return min(dp[0],dp[1]);

4.2 代码

4.2.1以i位置为终点

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        
        int n=cost.size();
        vector<int> dp(n+1);
        dp[0]=dp[1]=0;

        for(int i=2;i<=n;i++)
        {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
};

4.2.2以i位置为起点

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
      int n=cost.size();
     vector<int> dp(n);
     dp[n-1]=cost[n-1];
     dp[n-2]=cost[n-2];
     for(int i=n-3;i>=0;i--)
     {
       dp[i]=min(dp[i+1],dp[i+2])+cost[i];
    }
    return min(dp[0],dp[1]);
    }
};

5. 91.解码方法

5.1 分析

题目所述就是把一串数字反向解码为字母映射出来，有多少种方法。 题目也说，一个单独的数字可以映射的，但是这个数字前面是0的话就不可以。

来看看题目给的示例： 226就有三种解码方式：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6)

1. 状态表示 以i位置，要求的就是以i位置结尾方法的总数；
2. 状态表示方程： 来找解码到i位置时最近的一步，可以分成两种情况： （1）i这个位置单独解码； （2）i位置和i-1结合一起共同解码。这两种情况都会出现解码失败和成功的情况。 第一种（1）以i位置单独解码，如果这个数字在1-9之间，就能成功也就是有dp[i-1]种；如果失败就是0； 第二种（2）i位置和i-1结合一起共同解码，如果这两个数字结合在10-26之间，就解码成功，所以解码成功就是dp[i-2]，；解码失败就是0。

状态表示方程：dp[i]=dp[i-1]+dp[i-2]，都是成功时候才加。

1. 初始化: 要把0位置和1位置。以0位置结尾说明就只有一个字符，在1-9之间就成功就是1，如果失败就是0。 以1位置进位有三种情况： （1）两个字符都可以单独解码； （2）两个字母合在一起解码成功； （3）前面两种都不存在。它的解码数可能是0,1或者2。
2. 填表顺序： 从左往右
3. 返回值 这个字符串的解码方式，也就是到字符串i-1位置：dp[i-1]

优化：处理边界以及初始化问题 多开一个虚拟位置，有什么用呢？ 在旧的初始化列表中，初始化dp[1]是比较麻烦的，如果把它放在填表位置就会比较轻松。

得注意：1. 保证虚拟节点位置值是正确的；2.得注意下标映射关系 当要在新的dp表里面2的结果就要用到0和1位置的值。这里dp[0]=1,要想在2位置解码成功，那么0位置必须是解码成功的。 在新的dp表里面的i统一都对应把位置往后面移动了一位，这里在写代码的时候就得减1。

5.2 代码

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n);
        dp[0]=s[0]!='0';
        if(n==1)return dp[0];

        if(s[0]!='0'&&s[1]!='0') dp[1]+=1;

        int t=(s[0]-'0')*10+s[1]-'0';
        if(t>=10&&t<=26) dp[1]+=1;

        for(int i=2;i<n;i++)
        {
            if(s[i]!='0')dp[i]+=dp[i-1];
            int t=(s[i-1]-'0')*10+s[i]-'0';
            if(t>=10&&t<=26) dp[i]+=dp[i-2];
        }
        return dp[n-1];
    }
};

优化后：

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

有问题请指出，大家一起进步！！!