一定要早日上岸鸭 · August 8, 2021 0

1137. 第 N 个泰波那契数

1137. 第 N 个泰波那契数

递归+滑动数组优化:

class Solution { public int tribonacci(int n) { if(n==0) return 0; if(n==1) return 1; if(n==2) return 1; // 超时: // return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3); // 滑动数组优化: int p = 0, q = 0, r = 1, s = 1; for (int i = 3; i <= n; ++i) { p = q; q = r; r = s; s = p + q + r; } return s; } }