[Day 19] Leetcode 1137. N-th Tribonacci Number (C++)

前言

September LeetCoding Challenge 2021今天的题目是1137. N-th Tribonacci Number,跟DP最基础经典的费氏数列基本一样,只是多一个数字,就当作复习写写看吧!

想法

我们在Day 4的时候就有提过费氏数列的解法。可以来回顾一下最费时的方式就是recursive,我要求t(10)的时候就让他去呼叫t(9)+t(8)+t(7),然後每个又回去呼叫本题,写法如下:

class Solution {
public:
    int tribonacci(int n) {
        // use dp to save computed elements
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 1;
        }
        
        return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
    }
};

可以跑跑看体会一下时间感XD n每+1,时间是n倍数的在增加。
而经典的DP写法如下:

class Solution {
public:
    int tribonacci(int n) {
        // use dp to save computed elements
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 1;
        }
        vector<int> tri(n+1,0);
        tri[1]=1;
        tri[2]=1;
        for(int i=3;i<=n;++i){
            tri[i]=tri[i-1]+tri[i-2]+tri[i-3];
        }
        return tri[n];
    }
};

我们也有提到过其实每次只需要前三个数字,那我们也不需要维护一个n+1这麽大的table,只要每次保留最新的三组就好,节省一些些空间,如下:

class Solution {
public:
    int tribonacci(int n) {
        // use dp to save computed elements
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else if(n==2){
            return 1;
        }
        int t1=0;
        int t2=1;
        int t3=1;
        int ans=t1+t2+t3;
        for(int i=3;i<=n;++i){
            ans = t1+t2+t3;
            t1 = t2;
            t2 = t3;
            t3 = ans;
        }
        return ans;
    }
};

时间复杂度就是O(n),因为从2~n我们每次会进行O(1)运算。

结语

今天的题目很简单,就是DP系列的起点,还是要掌握好这个基本想法。


<<:  庄家 show hand 了? - 竭尽点 ?

>>:  DAY24 - [React hook] component 零组件

纯文组转职仔的路程。(第一个月)

Wie geht's? 我叫Albert,德语与英文名字都是一样的。 先来简单的自我介绍一下吧 我今...

予焦啦!Ethanol 记忆体映像规划

本节是以 Golang 上游 4b654c0eeca65ffc6588ffd9c99387a7e4...

[Day 03] if条件、缩排规则、函式写法,以及一些字串技巧

[ 30 Days of ML Challenge | D03] 今天提供一个文件以及一个练习教材,...

【Day10-去重】使用python优雅的一行解决list或DataFrame资料去重问题

前一天,我们简单讨论了一下面对缺失值资料的处理 那今天就反过来讨论一下面对资料中有重复的情况应该要怎...

Day 5 学习前人的隐私条款设计

Day 4提到过往我们如何拟出一份适用符合内部及市场的隐私条款,今天还是以隐私条款为主要探讨方向,在...