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

[动态规划] (一) LeetCode 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)