🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》《C++入门到进阶&自我学习过程记录》
《算法题讲解指南》--优选算法
《算法题讲解指南》--递归、搜索与回溯算法
《算法题讲解指南》--动态规划算法

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

---

目录

1.第 N 个泰波那契数

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法流程：

C++算法代码：

算法总结及流程解析：

2.三步问题

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

---

1.第 N 个泰波那契数

题目链接：

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法流程：

  1.状态表示：
      这道题可以「根据题目的要求」直接定义出状态表示：
      dp[ i ]表示:第 i 个泰波那契数的值。

  2.状态转移方程：
      题目已经非常贴心的告诉我们了：
      dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3 ]

  3.初始化：
      从我们的递推公式可以看出，dp[ i ]在 i = 0 以及 i = 1的时候是没有办法进行推导的，因为dp[-2]或dp[-1]不是一个有效的数据。
      因此我们需要在填表之前，将 0，1，2 位置的值初始化。题目中已经告诉我们 dp[ 0 ] = 0, dp[ 1 ] = dp[ 2 ] = 1。

  4.填表顺序：
      毫无疑问是「从左往右」。

  5.返回值：
      应该返回dp[ n ]的值。

C++算法代码：

class Solution {
public:
    int tribonacci(int n) 
    {
        //1、创建 dp 表
        //2、初始化
        //3、填表
        //4、返回值
        
        // vector<int> dp(n + 1);
        // //处理边界情况
        // if(n == 0 || n == 1)
        // {
        //     return n;
        // }    
        // if(n == 2)
        // {
        //     return 1;
        // }
        // dp[0] = 0, dp[1] = T[2] = 1;
        // for(int i = 3; i < n + 1; i++)
        // {
        //     dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        // }
        // return dp[n];

        //空间优化：
        if(n == 0 || n == 1)
        {
            return n;
        }    
        if(n == 2)
        {
            return 1;
        }
        int a = 0, b = 1, c = 1, d = 0;//通过滚动数组的逻辑只需要四个变量即可实现
        for(int i = 3; i < n + 1; i++)
        {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};

算法总结及流程解析：

2.三步问题

题目链接：

面试题 08.01. 三步问题 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

  1.状态表示：
      这道题可以根据「经验+题目要求」直接定义出状态表示：
      dp[ i ]表示：到达 i 位置时，一共有多少种方法。

  2.状态转移方程：
      以 i 位置状态的最近的一步，来分情况讨论:
      如果dp[i]表示小孩上第i阶楼梯的所有方式，那么它应该等于所有上一步的方式之和：
          i.上一步上一级台阶，dp[i] += dp[i - 1];
          ii. 上一步上两级台阶，dp[i] += dp[i-2];
          iii.上一步上三级台阶，dp[i] += dp[i- 3];
      综上所述，dp[i] =dp[i-1] + dp[i-2] + dp[i-3]。

      需要注意的是，这道题目说，由于结果可能很大，需要对结果取模。
      在计算的时候，三个值全部加起来再取模，即 (dp[i-1]+dp[i-2]+dp[i-3]) % MOD 是不可取的，同学们可以试验一下，n取题目范围内最大值时，网站会报错signed integer overflow 。
      对于这类需要取模的问题，我们每计算一次(两个数相加/乘等)，都需要取一次模。否则，万一发生了溢出，我们的答案就错了。

  3.初始化
      从我们的递推公式可以看出，dp[i]在i = 0，i = 1 以及i = 2 的时候是没有办法进行推导的，因为dp[-3] dp[-2] 或 dp[-1] 不是一个有效的数据。
      因此我们需要在填表之前，将1，2，3 位置的值初始化。
      根据题意，dp[1]=1，dp[2]= 2，dp[3]= 4 。

  4.填表顺序
      毫无疑问是「从左往右」。

  5.返回值
      应该返回 dp[n] 的值。

C++算法代码：

class Solution {
public:
    int waysToStep(int n) 
    {
        //1、创建 dp 表
        //2、初始化
        //3、填表
        //4、返回值
        
        if(n == 1 || n == 2)
        {
            return n;
        }
        int MOD = 1e9 + 7;
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }   
        return dp[n];
    }
};

算法总结及流程解析：

结束语

      到此，1.第 N 个泰波那契数，2.三步问题 这两道算法题就讲解完了。第N个泰波那契数，通过状态转移方程dp[i]=dp[i-1]+dp[i-2]+dp[i-3]求解，给出了完整实现和空间优化版本；三步问题，分析到达第i阶的方法数dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，强调取模运算的注意事项。希望大家能有所收获！