每日一道leetcode
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
题目
泰波那契序列 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
提示：
0 <= n <= 37- 答案保证是一个 32 位整数，即
answer <= 2^31 - 1。
思路
- 这题主要就是了解一下动态规划的机制，即当前节点的计算不用从头开始，直接继承前几个节点的状态即可。
- 所以只用考虑好边界情况，即当n<=2时，需要把3个初始值给直接输出；一旦n>2，则进行n-3轮的动态更新Tn = Tn-3+Tn-2+Tn-1。
代码实现
class Solution {
public:int tribonacci(int n) {int t0, t1 = 1, t2 = 1, nxt;if(n == 0) return 0;else if(n == 1 || n == 2) return 1;else {for(int i = 3; i <= n; i++) {nxt = t0 + t1 + t2;t0 = t1;t1 = t2;t2 = nxt;}}return nxt;}
};复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
官方题解
- 先精简一下我的实现里的一些dirty的步骤，n==1 || n==2的部分可以改为n<=2，这样效率就高了（虽然完全影响不大hhh）。
- 有点逆天，竟然还真的有代码更长但是效率更高的解法，叫矩阵快速幂的实现方法，不过不想实现了，只写写思路。
- 首先看看官解的一个矩阵乘法的推导（感觉要构造这么个矩阵就已经超过我的数学基础了），首先以这么个构造来建立矩阵乘法，即通过堆M进行幂运算再与初始矩阵做矩阵乘最后取第三行（即下标为2）的值即可。
- 为什么说这是效率更高的计算，在于幂运算是可以将时间复杂度降到O(logn)的，那么相比于O(n)的动态规划确实就效率增长了，现在来看看这个算法的思路：
- 假设两种情况，n为奇数或n为偶数：
- 当n为奇数时，x^n = x*(x^(n-1)) = x*(x^((n-1)/2)*x^((n-1)/2)) = ...。
- 当n为偶数时，x^n = x^(n/2)*x^(n/2)) = ...。
- 那么每一次运算都能把运算数量减半，最后的总的时间复杂度就是O(logn)的了。
- 接下来就是实现了，首先得实现一个矩阵乘的函数，涉及9*3次乘法运算和9*2次加法运算以及9*1次赋值。
- 当n小于等于2时，直接送上初始值，如果大于2时，则开始矩阵的幂运算。
- 令x等于初始矩阵M，每次运算都让x = x * x，总共计算logn轮，通过n/2的结果来控制运算的边界（这里可以用过n>>1来更高效地达到同样的效果）。
- 若是递归实现，则最后当n=0时返回1作为最尾端的控制，其余情况当n为偶数是则递归调用x^(n/2)*x^(n/2)；当n为奇数时，则x*(x^((n-1)/2)*x^((n-1)/2))。
- 若是非递归实现，讲讲官解的实现吧：
- 每轮先判断(n&1) == 1，若是，则更新结果，否则不断地n>>1，并矩阵乘更新矩阵，直到n<=0停止。那么每轮当是奇数的时候，单独对结果进行一次单独乘上一轮矩阵的行为，不影响矩阵幂乘的过程。如果是偶数时，到最后也会到达1，会将最后的矩阵直接乘给ret。
- 具体看官解的实现（我感觉还挺巧妙的，但是要想想）：
