解法: 动态规划
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] 的值。
class Solution
{
public:
int tribonacci(int n)
{
// 创dp表
vector<int> dp(n + 1);
// 初始化
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];
}
};