[数据结构与算法]1137. 第 N 个泰波那契数 | 动态规划 | 暴力递归 | 自顶向下

力扣打卡：1137. 第 N 个泰波那契数

解题思路

其实最重要的是怎么写出来暴力递归的方法

• 重要的是不要在写暴力递归时，想着任何的优化操作
• 重要的是不要在写暴力递归时，想着怎么定义函数
• 重要的是理解：自己定义的函数就是能够得到子问题的结果，需要什么子问题的结果，直接调用就可以了
• 不要怀疑这个函数能不能得到结果，如果不能，那么定义这个函数做什么呢？
• 直接调用函数，得到的就是子问题的结果，然后与当前的状态进行联系就可

代码

class Solution {
    public int tribonacci(int n) {
        // 先写出暴力递归的方式
        // 分析：每一个数都是前一个数和前两个数和前三个数的和，那么当前的问题和子问题的关系就是，当前的数等于之前的三个数的和
        // 定义一个函数，能够得到前一个数和前两个数和前三个数，定义的功能就是这个，直接调用函数即可得到前一个和前两个和前三个
        // return planA(n);

        int[] memo = new int[n+1]; // 此时memo的元素都是与题目无关的数据
        return planB(memo, n);
    }

    public int planA(int n){
        if(n==0) return n; // basecase
        if(n==1 || n==2) return 1; // basecase

        return planA(n-1) + planA(n-2) + planA(n-3); // 等于前一个数和前两个数的和

    }

    // 将暴力递归写出来后，那么自顶向下的动态规划就是增加了判断和记录的过程
    public int planB(int[] memo, int n){
        if(n==0) return 0;
        if(n==1 || n==2) return 1; // basecase

        if(memo[n] != 0) return memo[n];

        memo[n] = planB(memo, n-1) + planB(memo, n-2) + planB(memo, n-3); // 将此时的结果记录下来

        return memo[n];
    }
}