[动态规划] (一) LeetCode 1137.第N个泰波那契数

[动态规划] (一) LeetCode 1137.第N个泰波那契数

1137. 第 N 个泰波那契数

题目解析

解题思路

状态表示

(1) 题目要求

(2) 经验+题目要求

(3) 分析问题发现重复子问题

dp[i]的含义：dp[i]表示第N个泰波纳切数。

状态转移方程

由题意得：

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

初始化和填表顺序

初始化：填表时保证不越界

填表顺序：保证之前的状态已经计算过了，所以是从左向右

返回值

题目要求+状态表示

返回第n个泰波那契数：return dp[n]。

代码实现

class Solution {
public:int tribonacci(int n) {//处理边界情况if(n == 0) return 0;else if(n == 1 || n == 2) return 1;//1.创建dp表vector<int> dp(n+1);//2.初始化dp[0] = 0, dp[1] = 1, dp[2] = 1;for(int i = 3; i <= n; i++){//3.填表dp[i] = dp[i-1] + dp[i-2] + dp[i-3];}//返回值return dp[n];}
};

总结

细节1：注意处理边界情况。

细节2：开辟容器时初始化(n+1)个空间，数组下标从0开始。

细节3：遍历完整的n，i <= n。

时间复杂度：O(n)

空间复杂度：O(n)

空间优化

滚动数组：

dp[3] = dp[2] + dp[1] + dp[0]

dp[4] = dp[3] + dp[2] + dp[1],没有使用到dp[0]

dp[5] = dp[4] + dp[3] + dp[2],没有使用到dp[1], dp[0]。

造成了空间的浪费，所以我们可以定义4个变量a, b, c, d来循环写入dp[i]。

a = 0, b = 1, c = 1, d = a+b+c

a = b, b = c, c = d, d = a+b+c(如果反过来，就会让 a = b = c 和d一样了)

代码实现

class Solution {
public:int tribonacci(int n) {if(n == 0) return 0;else 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;}
};

总结

时间复杂度：O(N) 空间复杂度：O(1)