【动态规划刷题 1 】 第N个泰波那契数&& 三步问题

第N个泰波那契数

链接: 第N个泰波那契数

1137 . 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

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

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

示例 1：

输入：n = 4

输出：4

解释：

T_3 = 0 + 1 + 1 = 2

T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25

输出：1389537

1.状态表示

dp[i] 表示的是第 i 个泰波那契数的值。2.状态转移方程

动态规划题，我们需要学会依靠经验和题目解析去猜测他们的状态转移方程。

这一题题目已经告诉我们了。

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

3. 初始化

从我们的递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的，因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。

因此我们需要在填表之前，将0, 1, 2 位置的值初始化。题⽬中已经告诉我们

dp[0] = 0, dp[1] = dp[2] = 1 。

4. 填表顺序

按照数组下标的顺序，从左往右。

5. 返回值

应该返回 dp[n] 的值。

代码：

在写代码时按照此顺序：

1. 创建dp
2. 初始化
3. 填表
4. 返回值

   int tribonacci(int n) {
        vector<int> dp(n+1);
          if(n==0) return 0;
        if(n==1||n==2) return 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];
    }

三步问题

链接: 三步问题

面试题 08.01. 三步问题

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

输入：n = 3

输出：4说明: 有四种走法

示例2:

输入：n = 5

输出：13

1.状态表示

dp[i] 表示的是以 i 阶楼梯为结尾，小孩跳动到此处的方式数。

2.状态转移方程以i位置状态的最近的⼀步，来分情况讨论：

如果 dp[i] 表⽰⼩孩上第 i 阶楼梯的所有⽅式，那么它应该等于所有上⼀步的⽅式之和：

1. 从 i-1 处跳⼀级台阶， dp[i] +=  dp[i - 1] ；

1. 从 i-2 处跳两级台阶， dp[i] += dp[i - 2] ；
2. 从 i-3 处跳三级台阶， dp[i] += dp[i - 3] ；

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

3. 初始化

从我们的递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的，因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。

因此我们需要在填表之前，将0, 1, 2 位置的值初始化。我们可知

dp[1] = 1, dp[2] = 2，dp[3]=4;

4. 填表顺序

按照数组下标的顺序，从左往右。

5. 返回值

应该返回 dp[n] 的值。

代码

此题会存在数据溢出的问题，需要取模处理：

   int waysToStep(int n) {
         //创建dp
        //初始化
        //填表
        //返回值
         if(n<=2) return n;
        vector<int> dp(n+1);
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4;i<n+1;i++)
        {
          //取模
            dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;
        }
        return dp[n];
    }