比亚迪
随着华为（几乎是最晚一家）开奖，秋招基本也进入最后的尾声。
与网上那些动辄 20k+ 的 SP/SSP 玩家不同，今天看到一篇格外真实的帖子：
发帖的同学说到，随着秋招的结束，自己偷偷签下了比亚迪，虽然做的项目很有趣，但相比于自己的专业，仍然感觉自己是转行了。入职比亚迪的事儿，至今不敢告诉实验室的小伙伴和导师。除了专业不对口，还担心入职比亚迪会不被认可。
确实，比亚迪和其他互联网大厂不同，很少会根据面试者具体表现来划分「白菜/SP/SSP」几个档位，更多就是简单的按照「学历」来给 Offer。
这一模式也引发了很多同学的不满，感觉自己大学几年的努力都被无视了，导致比亚迪在应届生的侯选 List 中一直比较靠后，几乎就是鄙视链的底端。
但怎么说呢？适合自己的才是最好的。
每年应届生这么多，哪能个个都拿头牌大厂的 SP？
尤其对于应届生来说，首份工作对于"成长性"的考量应当是要高于"薪资待遇"方面的，而且「应届校招」也是「选择加入自己喜欢的行业（转行）」的最好时机。
要知道，如果毕业几年后，再想加入某个行业，可没有校招路线可走。社招对行业经验的要求几乎是不可避免的，即使通过"特训"手段，通过了面试，混入了某个公司，也不会有人把你当成白纸来培养，因此在工作中得到系统成长的机会几乎为零。
...
回归主题。
来一道玩法繁多的算法题，看你能撑到第几关。
题目描述
平台：LeetCode
题号：1137
泰波那契序列 定义如下：
, , , 且在 的条件下
给你整数 ，请返回第 个泰波那契数 的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
提示：
答案保证是一个 位整数，即 。
动态规划（迭代）
都直接给出状态转移方程了，其实就是道模拟题。
使用三个变量，从前往后算一遍即可。
Java 代码：
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;
for (int i = 3; i <= n; i++) {
int d = a + b + c;
a = b; b = c; c = d;
}
return c;
}
}
C++ 代码：
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;
for (int i = 3; i <= n; i++) {
int d = a + b + c;
a = b; b = c; c = d;
}
return c;
}
};
Python 代码：
class Solution:
def tribonacci(self, n: int) -> int:
if n == 0: return 0
if n == 1 or n == 2: return 1
a, b, c = 0, 1, 1
for i in range(3, n + 1):
d = a + b + c
a, b, c = b, c, d
return c
TypeScript 代码：
function tribonacci(n: number): number {
if (n === 0) return 0;
if (n === 1 || n === 2) return 1;
let a = 0, b = 1, c = 1;
for (let i = 3; i <= n; i++) {
const d = a + b + c;
a = b; b = c; c = d;
}
return c;
};
时间复杂度： 空间复杂度：
动态规划（递归）
也就是记忆化搜索，创建一个 cache 数组用于防止重复计算。
Java 代码：
class Solution {
int[] cache = new int[40];
public int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
if (cache[n] != 0) return cache[n];
cache[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
return cache[n];
}
}
C++ 代码：
class Solution {
public:
vector<int> cache = vector<int>(40, 0);
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
if (cache[n] != 0) return cache[n];
cache[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
return cache[n];
}
};
Python 代码：
class Solution:
def __init__(self):
self.cache = [0] * 40
def tribonacci(self, n: int) -> int:
if n == 0: return 0
if n == 1 or n == 2: return 1
if self.cache[n] != 0: return self.cache[n]
self.cache[n] = self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)
return self.cache[n]
时间复杂度： 空间复杂度：
矩阵快速幂
这还是一道「矩阵快速幂」的板子题。
首先你要对「快速幂」和「矩阵乘法」概念有所了解。
矩阵快速幂用于求解一般性问题：给定大小为 的矩阵 ，求答案矩阵 ，并对答案矩阵中的每位元素对 取模。
在上述两种解法中，当我们要求解 时，需要将 到 都算一遍，因此需要线性的复杂度。
对于此类的「数列递推」问题，我们可以使用「矩阵快速幂」来进行加速（比如要递归一个长度为 的数列，线性复杂度会被卡）。
使用矩阵快速幂，我们只需要 的复杂度。
根据题目的递推关系（）：
我们发现要求解 ，其依赖的是 、 和 。
我们可以将其存成一个列向量：
当我们整理出依赖的列向量之后，不难发现，我们想求的 所在的列向量是这样的：
利用题目给定的依赖关系，对目标矩阵元素进行展开：
那么根据矩阵乘法，即有：
我们令
然后发现，利用 我们也能实现数列递推（公式太难敲了，随便列两项吧）：
再根据矩阵运算的结合律，最终有：
从而将问题转化为求解 ，这时候可以套用「矩阵快速幂」解决方案。
Java 代码：
class Solution {
int N = 3;
int[][] mul(int[][] a, int[][] b) {
int[][] c = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
}
}
return c;
}
public int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int[][] ans = new int[][]{
{1,0,0},
{0,1,0},
{0,0,1}
};
int[][] mat = new int[][]{
{1,1,1},
{1,0,0},
{0,1,0}
};
int k = n - 2;
while (k != 0) {
if ((k & 1) != 0) ans = mul(ans, mat);
mat = mul(mat, mat);
k >>= 1;
}
return ans[0][0] + ans[0][1];
}
}
C++ 代码：
class Solution {
public:
int N = 3;
vector<vector<long long>> mul(vector<vector<long long>>& a, vector<vector<long long>>& b) {
vector<vector<long long>> c(N, vector<long long>(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
}
}
return c;
}
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
vector<vector<long long>> ans = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
vector<vector<long long>> mat = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
int k = n - 2;
while (k != 0) {
if ((k & 1) != 0) ans = mul(ans, mat);
mat = mul(mat, mat);
k >>= 1;
}
return ans[0][0] + ans[0][1];
}
};
Python 代码：
class Solution:
def __init__(self):
self.N = 3
def mul(self, a, b):
c = [[0] * self.N for _ in range(self.N)]
for i in range(self.N):
for j in range(self.N):
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j]
return c
def tribonacci(self, n: int) -> int:
if n == 0: return 0
if n == 1 or n == 2: return 1
ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
mat = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
k = n - 2
while k != 0:
if k & 1: ans = self.mul(ans, mat)
mat = self.mul(mat, mat)
k >>= 1
return ans[0][0] + ans[0][1]
TypeScript 代码：
function tribonacci(n: number): number {
const N = 3;
const mul = function(a: number[][], b: number[][]): number[][] {
const c = Array.from({ length: N }, () => Array(N).fill(0));
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
}
}
return c;
};
if (n === 0) return 0;
if (n === 1 || n === 2) return 1;
let ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]];
let mat = [[1, 1, 1], [1, 0, 0], [0, 1, 0]];
let k = n - 2;
while (k !== 0) {
if (k & 1) ans = mul(ans, mat);
mat = mul(mat, mat);
k >>= 1;
}
return ans[0][0] + ans[0][1];
};
时间复杂度： 空间复杂度：
打表
当然，我们也可以将数据范围内的所有答案进行打表预处理，然后在询问时直接查表返回。
但对这种题目进行打表带来的收益没有平常打表题的大，因为打表内容不是作为算法必须的一个环节，而直接是作为该询问的答案，但测试样例是不会相同的，即不会有两个测试数据都是 。
这时候打表节省的计算量是不同测试数据之间的相同前缀计算量，例如 和 ，其 之前的计算量只会被计算一次。
因此直接为「解法二」的 cache 添加 static 修饰其实是更好的方式：代码更短，同时也能起到同样的节省运算量的效果。
Java 代码：
class Solution {
static int[] cache = new int[40];
static {
cache[0] = 0; cache[1] = 1; cache[2] = 1;
for (int i = 3; i < cache.length; i++) {
cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3];
}
}
public int tribonacci(int n) {
return cache[n];
}
}
C++ 代码：
class Solution {
public:
static vector<long long> cache;
Solution() {
cache.resize(40);
cache[0] = 0; cache[1] = 1; cache[2] = 1;
for (int i = 3; i < 40; ++i) {
cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3];
}
}
int tribonacci(int n) {
return static_cast<int>(cache[n]);
}
};
vector<long long> Solution::cache;
Python 代码：
class Solution:
cache = [0, 1, 1] + [0] * 37
for i in range(3, 40):
cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3]
def tribonacci(self, n: int) -> int:
return self.cache[n]
时间复杂度：将打表逻辑交给 ，复杂度为 ， 固定为 。将打表逻辑放到本地进行，复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
