每日OJ题_斐波那契dp①_力扣1137. 第 N 个泰波那契数

目录

动态规划dp算法原理

力扣1137. 第 N 个泰波那契数

解析代码1

解析代码2

---

动态规划dp算法原理

        动态规划（Dynamic Programming）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

        动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

        与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上）。

（除此斐波那契dp外还有其它类型的dp在后面会更新。）

动态规划算法解决问题的分类：

动态规划dp算法一般步骤：

1. 确定状态表示（dp[ i ] 表示什么，一般以 i 位置为起点或结尾分析，化成子问题）
2. 状态转移方程（斐波那契数列的状态转移方程为：dp[i] = dp[i-1] + dp[i-2]）
3. 初始化（斐波那契数列初始化可以为dp[0] = 0, dp[1] = 1;）
4. 填表顺序（斐波那契数列从左往右填）
5. 返回值（如果斐波那契数列要求是第 n 个斐波那契数，返回dp[ n ] 即可）

---

力扣1137. 第 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

提示：

• 0 <= n <= 37
• 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

class Solution {
public:
    int tribonacci(int n) {
 
    }
};

---

解析代码1

简单的DP，根据题目已经得到状态转移方程了：

class Solution {
public:
    int tribonacci(int n) {
            if(n <= 1) // 处理边界
                return n;
 
            vector<int> dp(n+1, 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];
    }
};

---

解析代码2

        滚动数组对解法1进行空间上的优化，后面类似的空间优化就不写了，因为笔试没用，面试能讲出来就行。

class Solution {
public:
    int tribonacci(int n) {
            if(n <= 1) // 处理边界
                return n;
 
            int a = 0, b = 1, c = 1, d = 1; // 滚动数组思想优化空间
            for(int i = 3; i <= n; ++i)
            {
                d = a + b + c;
                a = b;
                b = c;
                c = d;
            }
            return d;
    }
};