Re: [閒聊] 每日leetcode

[yam276 (史萊哲林的優等生)]

※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/n-th-tribonacci-number/description
: 1137. N-th Tribonacci Number
: 給你一個數字n，求出第 n 個 Tribonacci 數列是多少。
: 思路：
: 1.動態規劃，然後把空間壓一壓。

動態規劃基礎題

然後Vec要根據n+來創 i32記得轉換成usize


最常見的方法：

Code:

impl Solution {
    pub fn tribonacci(n: i32) -> i32 {
        if n == 0 { return 0; }
        if n == 1 || n == 2 { return 1; }

        let mut dp = vec![0; (n+1) as usize];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for i in 3..=n as usize{
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        dp[n as usize]
    }
}


別人的三數字壓空間寫法

可以0ms 1.96MB 都100%

impl Solution {
    pub fn tribonacci(n: i32) -> i32 {
        if n < 2 {
            return n;
        }

        let mut dp = vec![0, 1, 1];

        for i in 3..=n {
            let next = dp[0] + dp[1] + dp[2];
            dp[0] = dp[1];
            dp[1] = dp[2];
            dp[2] = next;
        }

        dp[2]
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713928298.A.876.html
※ 編輯: yam276 (60.248.143.163 臺灣), 04/24/2024 11:17:46