【算法挨揍日记】day17——1137. 第 N 个泰波那契数、面试题 08.01. 三步问题

柔光的暖阳◎ 2024-02-21 11:48 39阅读 0赞

![759286e2e1c1423393348ccb1879d427.png][]

## 1137. 第 N 个泰波那契数 ##

[1137. 第 N 个泰波那契数][1137. _ N]

### 题目描述： ###

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

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

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

![df64f56d59f04ffd9f10273999031dad.png][]

### 解题思路： ###

> 本题很明显
> 
> 1.  状态表示dp【i】为第n个泰波那契数，![52fb8d2a24b8492482361d49c9db1e10.png][]本题是第一种情况，后面的题目我们会不断遇到1，2，3的情况，我们后面再细讲
> 2.  而状态转移方程为题目也直接给了出来， Tn+3 = Tn + Tn+1 + Tn+2，状态转移方程： Tn = Tn -1+ Tn-2 + Tn-3
> 3.  初始化（防止越界的情况）：本题很明显Tn-3的时候当，n小于3的时候会出现越界的情况，因此我们要提前初始化好dp【0】 ，dp【1】，dp【2】
> 4.  填表顺序： 左到右![462ab0769d274709b4ac55d862108fc2.png][]
> 5.  返回值；dp【n】
> 
> 细节问题：
> 
>  *  当n<3的时候，就不需要进行Tn = Tn -1+ Tn-2 + Tn-3计算因此就可以直接返回
> 
> 空间优化问题：
> 
> 本题如果我们按照上面的写法的话，就需要开辟一个n+1大小的vector数组dp，当我们在计算第n个位置的时候，我们只需要n-1，n-2，n-3的位置，如果前面还有n-4和n-5都不需要的
> 
> ![10eef0b5353c418cbc8d4ea3ec68adfe.png][]
> 
> 因此我们就可以直接用三个变量a，b，c来优化，使得空间复杂度为o(1)

### 解题代码： ###

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] = 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;
            int d = 0;
            for (int i = 3; i <= n; i++)
            {
                d = a + b + c;
                a = b; b = c; c = d;
            }
            return d;
        }
    };

--------------------

## 面试题 08.01. 三步问题 ##

[面试题 08.01. 三步问题][08.01.]

### 题目描述： ###

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

![2d19a0f65df34204b69efa84a6412967.png][]

### 解题思路： ###

> 分析一下题目的意思：
> 
> 当从0号台阶到1号台阶，只有1种方法；
> 
> 当从0号台阶到2号台阶，我们可以直接从0号台阶蹦到2号台阶，也可以从0-1-2，总共两种解法
> 
> 当从0号台阶到3号台阶，我们可以从0号直接蹦到3号台阶，也可以0-1-2-3和0-2-3和0-1-3，总共4种解法
> 
> ![c78475899bc647289bb1616543770d30.png][] 眼尖的同学这个时候以及发现了状态转移方程了，我们注意一下（以到4号台阶为例）：我们可以看成从1号到4的方法数+2号到4号的方法数+3号到4号的方法数
> 
> 1.  因此我们的状态表示dp【i】就表示到达第i号台阶的方法数
> 2.  状态转移方程：![772f0ec0c2a8401c9d87709d53675775.png][]
> 
> 此时有的同学会有一个疑问：就是我从i-2号台阶到i号台阶的时候不是有两种情况：
> 
>  *  i-2到i
>  *  i-2先到i-1再到i号台阶
> 
> 其实不然：i-2先到i-1的这种情况以及是包含在i-1到i的方法数中
> 
> 1.  初始化（防止越界的情况）：本题很明显Tn-3的时候当，n小于3的时候会出现越界的情况，因此我们要提前初始化好dp【0】 ，dp【1】，dp【2】
> 2.  填表顺序： 左到右
> 3.  返回值；dp【n】

### 解题代码： ###

class Solution {
    public:
        const int MOD=1e9+7;
        int waysToStep(int n) {
            if(n==1)return 1;
            if(n==2)return 2;
            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];        
        }
    };

![92bb6c4047d147a8a164ceb7a71d2a4e.gif][]

[759286e2e1c1423393348ccb1879d427.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/3744804ae3b44cd2b7c3a8f425399156.png
[1137. _ N]: https://leetcode.cn/problems/n-th-tribonacci-number/
[df64f56d59f04ffd9f10273999031dad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/544daa6fa7694acca1f7459300fb907b.png
[52fb8d2a24b8492482361d49c9db1e10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/64d993870ae949ad80bd635edb4b6886.png
[462ab0769d274709b4ac55d862108fc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/3447a9853caa4fe188434eaa46047124.png
[10eef0b5353c418cbc8d4ea3ec68adfe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/ab3abb49c2be4390a91abd5f71ba8baf.png
[08.01.]: https://leetcode.cn/problems/three-steps-problem-lcci/
[2d19a0f65df34204b69efa84a6412967.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/c6f54d407a50491d8756866ee4f32e91.png
[c78475899bc647289bb1616543770d30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/b76dffd3d97445b182000da313cfe4a2.png
[772f0ec0c2a8401c9d87709d53675775.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/1ffd3ecf15cf46bc8e53d3739c3c1a27.png
[92bb6c4047d147a8a164ceb7a71d2a4e.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/1cd1508deb3b4545aa7f82066ef6fb2c.png