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

Welcome to 9ilk's Code World

(๑•́ ₃ •̀๑) 个人主页: 9ilk

(๑•́ ₃ •̀๑) 文章专栏：算法Journey

🏠 第N个泰波那契数模型

📌 题目解析

第N个泰波那契数

题目要求的是泰波那契数，并非斐波那契数。

📌 算法原理

🎵 递归

函数设置：我们可以设置一个Taibo()函数，它能帮我们求出第n个泰波那契数。

函数返回值：题目保证answer <= 2^31 - 1，设置为int即可。

函数实现：根据定义求泰波那契数,我们需要前三个的泰波那契数相加,也就是Taibo(n-3) + Taibo(n-2) + Taibo(n-1)。

函数边界条件：对于n = 0,1,2是边界情况，我们可以提前处理。

参考代码：

class Solution {
public:
    long Taibo(int n)
    {
         if(n == 0)
         return 0;
         if(n == 1 || n == 2)
           return 1;
        return Taibo(n-1) + Taibo(n-2) + Taibo(n-3);
    }
    int tribonacci(int n)
    {
       return Taibo(n);
    }
};

🎵 记忆化搜索

对于解法一存在下面的问题：

我们发现在递归过程有的节点的值(比如上图的Taibo(3))在第3层就已经求得了，但是其他节点递归深入时又重新计算了，导致了不必要的时间和栈空间的开销(时间复杂度：O(3^n),空间复杂度：O(N))。本题虽然n最大为37，但其实栈空间和时间开销已经很大了，肯定会超时，我们可以采取记忆化搜索的方法：

1. 添加一个备忘录。

2. 每次递归返回时，将结果放到备忘录里面。

3. 在每次进入递归时，往备忘录里查询是否已经记录。

参考代码：

class Solution {
public:
    vector<int> memory;
    long Taibo(int n)
    {
        if (memory[n] != -1) //查看备忘录
            return memory[n];
        long ret = Taibo(n - 1) + Taibo(n - 2) + Taibo(n - 3);;
        memory[n] = ret; //存进备忘录
        return ret;
    }
    int tribonacci(int n)
    {
        memory.resize(38, -1); //创建一个备忘录
        memory[0] = 0;
        memory[1] = memory[2] = 1;
        return Taibo(n);
    }
};

此时比之前大大避免了不必要的时间开销，时间复杂度是(n)。

🎵 动态规划

我们动态规划分为以下几步：

1. 状态表示：

所谓状态表示其实是dp表里每个值代表的含义。

Q：状态从何而来？

题目要求(比如本题已经告诉我们要求的是第n个泰波那契数)。
经验 + 题目要求(后面我们再提)。
分析问题的过程，发现重复的子问题。

因此，本题dp[i]的含义是第i个泰波那契数。

2. 状态转移方程：

状态转移方程回答的是dp[i]怎么得到的问题，一般我们从"最近一步"得到。

比如本题中，由定义知，在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2，不就是dp[i] = dp[i-1] + dp[i-2] + dp[i-3]吗？

3. 初始化：

初始化保证我们填表的时候不发生越界！

当遇到n=2时，此时n-3=-1很明显会会发生越界，因此对于边界情况，我们可以提前确定好边界位置在dp表中的值，即dp[0] = 0, dp[1] = dp[2] = 1。

4. 填表顺序：

动态规划需要状态的推导，只有确定好填表顺序，才能确保在填写当前状态时，所需要的状态已经计算过了。

本题很明显是从左往右填表。

5. 返回值：

我们需要根据题目要求+状态表示来确定返回值。

注：dp[i]不一定就是我们所需的返回值，我们还需结合题目要求，本题dp[n]就是我们需要的返回值。

参考代码：

class Solution 
{
public:
   
    int tribonacci(int n)
     {
        //1.状态表示：dp[i]表示第N个泰波那切数
        vector<int> dp(38,-1);
        //2.初始化
         dp[0] = 0;
         dp[1] = dp[2] = 1;
        //3.填表
        for(int i = 3 ; i <= n ; i ++)
        {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];//4.状态转移方程
        } 
        return dp[n];//5.返回值
     }
};

时间复杂度：O（N）

空间复杂度：O（1）

🎵 滚动数组

我们用vector容器来模拟dp表，但其实可以进一步优化，当求dp[i]只有前面的若干个状态，最前面的几个状态不需要浪费空间，此时可以使用滚动数组优化！

我们可以利用四个变量来储存最近一次求泰波那契数的四个状态，不断进行滚动，最终求得目标结果！

注：对于赋值顺序，不能从右往左赋，即c = d,b = c, a = b因为d给c之后，c被d覆盖了，但是b想要的是c的，而c原本的值被覆盖了！

参考代码：

class Solution 
{
public:
    int tribonacci(int n)
    {
        //1.状态表示：dp[i]表示第N个泰波那切数
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 0;
        int b = 1;
        int c = 1;
        int d = 0;
        //3.填表
        for (int i = 3; i <= n; i++)
        {
            d = a + b + c;;//状态转移方程
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};

🏠 三步问题

📌 题目解析

三步问题

📌 算法原理

1. 状态表示(经验 + 题目要求)：

状态表示：dp[i]表示到达i位置时，一共有多少种方法。

2. 状态转移方程：

我们从i位置的状态，最近的一步来划分问题，由于小孩一次可以上1阶，2阶，3阶：

从i-1位置上来，此时dp[i] += dp[i-1]。
从i-2位置上来，此时dp[i] += dp[i-2]。
从i-3位置上来，此时dp[i] += dp[i-3]。

因此状态转移方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

3. 初始化：

对于第1，2，3级的台阶，取它们的最近状态可能会造成数组越界(比如i为2时，i-3得-1会越界)，因此我们可以提前设置好它们的状态：dp[1] = 1 , dp[2] = 2，dp[3] = 4。

4. 填表顺序：

由状态转移方程知，我们i位置的状态依赖于前几个位置的状态，因此我们填表顺序是从左往右填。

5.返回值：

我们要求的是上到第n阶楼梯的总方法，直接返回dp[n]即可，注意要对结果模1000000007。

参考代码：

class Solution 
{
public:
    int waysToStep(int n)
    {
         if(n == 1 || n == 2) return n;
         if(n == 3) return 4;
         long a = 1; //dp[1]
         long b = 2; //dp[2] 
         long c = 4; //dp[3]
         long d = 0; 
         for(int i = 4 ; i <= n ; i ++) //空间优化
         {
            d = (a + b + c)%1000000007; //状态转移方程
            a = b;
            b = c;
            c = d;
         }      
         return d;
    }
};

🏠 最小花费爬楼梯

📌 题目解析

最小花费爬楼梯

假设n为数组元素个数，则本题中楼梯顶部指的是dp[n]，并非dp[n-1]。

📌 算法原理

🎵 解法一 (以i位置为结尾)

1. 状态表示：

dp[i]表示:到达 i 位置时,所需支付的最少费用。

2. 状态转移方程：

用i位置的最近一步(之前或之后的状态)，推导出dp[i]的值。

当到达i-1位置时，支付cost[i-1],走一步到达i位置 -> dp[i-1] + cost[i-1]。
当到达i-2位置时，支付cost[i-2],走两步到达i位置 -> dp[i-2] + cost[i-2]。
我们要么选择从i-1位置到i，要么选择从i-2位置到i，我们要的是最小花费，则选最小的即可。

因此状态转移方程：dp[i] = min(dp[i-1]+cost[i-1] , dp[i-2] + cost[i-2])。

3.初始化

我们需要保证填表的时候不越界，本题可以选择从下标为0或下标为1的位置开始爬楼梯，因此这两个位置最初的花费是0，即dp[0] = dp[1] = 0。

4. 填表顺序

根据我们的状态转移方程，我们需i位置之前的状态，因此填表顺序是从左往右填。

5. 返回值

返回达到楼梯顶部的最低花费,返回dp[n]即可。

参考代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        if(n == 1 || n == 0) 
          return  0;
        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]; //返回值
    }
};

🎵 解法二 (以i位置为起点)

1. 状态表示：

dp[i]表示:从i位置出发,所需支付的最少费用。

2. 状态转移方程：

用i位置的最近一步(之前或之后的状态)，推导出dp[i]的值。

支付cost[i], 往后走一步,从i+1的位置出发到终点 -> dp[i+1] + cost[i]
支付cost[i], 往后走两步,从i+2的位置出发到终点 -> dp[i+2] + cost[i]
我们从i位置要么选择走一步到终点，要么选择走两步到终点,我们要的是最小花费，则选最小的即可。

因此状态转移方程：dp[i] = min(dp[i+1] + cost[i] , dp[i+2] + cost[i])。

3.初始化

对于n-1位置和n-2位置作为出发点,此时他们走一步或两步就到顶部了,因此i+1和i+2会使他们越界,我们只需支付他们对应的cost即可,即dp[n-1] = cost[n-1] && dp[n-2] = cost[n-2]。

4. 填表顺序

根据我们的状态转移方程，我们需i位置之后的状态，因此填表顺序是从右往左填。

5. 返回值

我们是从0或1位置为起点出发的，我们返回两者最小即可，即min(dp[0],dp[1])。

参考代码：

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

🏠 解码方法

📌 题目解析

91. 解码方法 - 力扣（LeetCode）

本题可能存在无法解码的字符串。
字符串中可能包含前导0。

📌 算法原理

1.状态表示：

根据经验+题目要求，我们可以设置dp[i]的状态：字符串以i位置结尾时，解码方法的总数。

2. 状态转移方程：

我们还是按照最近一步来划分问题，对于i位置的解码我们以下两种情况：

(1) s[i] 单独解码：

解码成功('1' <= s[i] <= '9',‘0’无法参与解码),此时解码总方法等于前一个位置的解码方法总数，即dp[i-1]。
解码失败，此时为0。

(2) s[i] 与 s[i-1]解码

解码成功(0 <= b*10+a <= 26)，时解码总方法等于第i-2个位结尾字符串的解码方法总数，即dp[i-2]。
解码失败，此时为0。

因此状态转移方程为：dp[i] = dp[i-1] + dp[i-2]

3. 初始化：

(1) i = 0时，位于字符串的第一个字符，我们只需判断它单独解码情况是否成立，取值可能为0，1。

(2) i = 1时，位于字符串的第二个字符，首先要单独解码就得先判断第一个字符能否单独解码否则没意义，能单独解码则dp[1]++；再判断与s[0]是否能解码，能则dp[1]++。其可能取值为0，1，2。

4. 状态转移方程：

根据状态转移方程，我们需要之前位置的状态，因此填表顺序是从左往右。

5. 返回值：

由题意得，最终需要的是以size-1为位置结尾的字符串的所有解码方法，因此返回dp[size-1]。

参考代码：

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;//s[1]单独解码
        int t = (s[0]-'0')*10 + s[1] - '0'; 
        if(t >= 10 && t <= 26) dp[1] += 1 ;//s[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] += 1;
        }
       return dp[n-1];
    }
};

🎵 优化(虚拟节点)

Q：我们发现这两段代码相似度较高，处理逻辑是一样的，能不能把边界情况放进循环里处理呢？

这里我们介绍一下虚拟节点：

我们可以在原dp表基础上扩充一个位置,保证最后一个位置下标为n,这样在处理字符串中原来下标为0位置的字符时,它在新dp表的下标变为1,这样i-1就不会越界!但是同时要注意两个问题:

1. 虚拟节点里面的值,要保证后面的填表时正确的。(比如对于新dp表的0下标位置，我们要保证对于如果字符串第二个位置的字符能跟第一个字符解码，此时需要新dp表i-2位置的值，也就是dp[0]，此时我们需要设置它为1，表示存在第二个字符和第二个字符共同解码这一种解码方法)

2. 下标的映射关系：我们新dp表下标在原来基础上+1，但是s[i]的size并没有变化！

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';
注意映射关系s[1-1]下标映射关系
  for(inti=2;i<=n;i++)
 {
   if(s[i-1]!='0')dp[i]+=dp[i-1];//处理单独编码的情况
   int =(s[i-2]-'0')*10+s[i-1]-'0';//第二种情况所对应的数
   if(t>=10 &&t<=26)dp[i]+=dp[i] += dp[i - 2];
 }
   return dp[n];
}

完。