Re: [闲聊] 每日leetcode

楼主: yam276 ('_')   2024-04-24 11:11:36
※ 引述《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]
}
}

Links booklink

Contact Us: admin [ a t ] ucptt.com