站多多 福州网站建设,手机企业网站程序,广东深圳南山区,网站底部备案号代码[动态规划] (一) LeetCode 1137.第N个泰波那契数 文章目录 [动态规划] (一) LeetCode 1137.第N个泰波那契数题目解析解题思路状态表示状态转移方程初始化和填表顺序返回值 代码实现总结空间优化代码实现 总结 1137. 第 N 个泰波那契数 题目解析 解题思路
状态表示
(1) 题目要…[动态规划] (一) 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表vectorint dp(n1);//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开辟容器时初始化(n1)个空间数组下标从0开始。
细节3遍历完整的ni 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 abc
a b, b c, c d, d abc(如果反过来就会让 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)
