LeetCode刷题-第N个泰波那契数

前言说明

算法学习，日常刷题记录。

题目连接

第N个泰波那契数

题目内容

泰波那契序列Tn定义如下：

T0 = 0，T1 = 1，T2 = 1，且在n >= 0的条件下Tn+3 = Tn + Tn+1 + Tn+2

给你整数n，请返回第n个泰波那契数Tn的值。

示例1:

输入：n = 4

输出：4

解释：

T_3 = 0 + 1 + 1 = 2

T_4 = 1 + 1 + 2 = 4

示例2:

输入：n = 25

输出：1389537

提示：

0 <= n <= 37

答案保证是一个32位整数，即answer <= 2^31 - 1。

分析过程

看到这里想到上一篇文章：爬楼梯

爬楼梯问题可转化为斐波那契数列，在上一篇文章中探讨过不能用递归法，因为会超时。

这道题是泰波那契数，和斐波那契数不同的是，斐波那契数是等于前两个数相加，泰波那契数是等于前三个数相加，不过没有多大区别。

前面的爬楼梯最后使用的是迭代法，这道题我们依然使用递归法，但使用带有记忆的递归法，比单纯的递归法节省运行时间。

定义一个集合map来保存结果，在递归方法里，每次都先从集合map中寻找有无保存好的结果，如果有，从集合map中直接取，如果没有，根据规则计算得出结果，把结果保存进集合map中，后面会被使用到，这样能减少递归时重复的操作。

解答代码

所以带有记忆的递归法，代码如下：

class Solution {
    public int tribonacci(int n) {
        // 直接调用递归方法
        return getTribonacci(n);
    }

    // 定义集合map保存结果
    private Map<Integer, Integer> map = new HashMap<>();

    // 递归法，带有记忆的递归，如果不带记忆，当n的值比较大时会运行超时
    private int getTribonacci(int n) {
        if (n == 0) {
            return 0;
        }

        if (n == 1 || n == 2) {
            return 1;
        }

        // 若集合map中找到key为n的value，直接返回value
        if (map.get(n) != null) {
            return map.get(n);
        }

        // 计算当前值，当前值等于前三个相加，注意这里必须先计算n-3，再计算n-2，最后计算n-1，因为前面计算出的结果，后面可以直接用
        int n1 = getTribonacci(n - 3);
        int n2 = getTribonacci(n - 2);
        int n3 = getTribonacci(n - 1);

        // 把n的当前值推进集合map中
        map.put(n, n1 + n2 + n3);

        // 最后从集合map中找到n的当前值
        return map.get(n);
    }
}

提交结果

执行用时0ms，时间击败100.00%的用户，内存消耗35.1MB，空间击败64.91%的用户。

运行结果

原文链接

原文链接：第N个泰波那契数