Re: [閒聊] 每日LeetCode已回收
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
--
※ 發信站: 批踢踢實業坊(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
推
01/30 10:07,
2年前
, 1F
01/30 10:07, 1F
推
01/30 11:02,
2年前
, 2F
01/30 11:02, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 210 之 719 篇)：