Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

1137. N-th Tribonacci Number
泰波拿契數被定義如下：
F(0) = 0;
F(1) = 1;
F(2) = 1;
F(n) = F(n-1) + F(n-2) + F(n-3);
給予一個n，求出他的泰波拿契數。

思路：
1.定義就是狀態轉移方程把他寫成DP就好。

Java Code：
----------------------------------------
class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n < 3) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 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];
    }
}
----------------------------------------

空間複雜度優化：
----------------------------------------
class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        int n0 = 0, n1 = 1, n2 = 1;
        for (int i = 3; i <= n; i++) {
            int num = n0 + n1 + n2;
            n0 = n1;
            n1 = n2;
            n2 = num;
        }
        return n2;
    }
}
----------------------------------------

https://i.imgur.com/nyvEpjm.jpg

--
https://i.imgur.com/sjdGOE3.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.0.114 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675043838.A.96C.html
※ 編輯: Rushia (36.231.0.114 臺灣), 01/30/2023 09:58:37
推 pandix: 大師
推 SecondRun: 大師