动态规划第一题-----1.第 N 个泰波那契数（leetcode）

用户11288958

发布于 2025-07-24 08:44:44

10100

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

动态规划做题思路

1.建一个dp表（Dynamic Programming表）， 2.将它填满， 3.里面的某一个值就是最终返回结果

题目传送门

一、题目解析

求第n个数而第n个数 = 前三个数之和。

二、讲解算法原理

1.状态表示

dp表中某一个值的含义就是状态表示 怎么来的？ 1. 看题目要求，只能解决简单题 2. 经验 + 题目要求 3. 分析问题的过程中，发现重复子问题。把重复子问题抽象为状态表示 ............先重点掌握这三个

dp【i】表示第 i 个泰波那契数的值

2.状态转移方程

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

3.初始化

保证填表的时候不越界

dp[0] = 0 dp[1] = dp[2] = 1

4.填表顺序

为了填写当前状态的时候，所需要的状态已经计算过了

从左向右

5.返回值

题目要求+状态表示

dp【n】

三、编写代码

1.创建dp表

2.初始化

3.填表

4.返回值

class Solution {
    public int tribonacci(int n) {
        //处理边界条件
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        //创建dp表
        int[] dp = new int[n+1]; 
        dp[0] = 0;dp[1] = dp[2]=1;

        for(int i = 3; i <= n; i++){              
            dp[i] = dp[i-1] + dp[i-2] +dp[i-3];
        }
        return dp[n];
    }
}

四、空间优化

当我们填一个数组的时候，当前值只需要前面若干个数，就可以用滚动数组进行优化

优化结果

class Solution {
    public int tribonacci(int n) {
        //处理边界条件
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        //创建滚动数组变量
        int a = 0,b = 1,c = 1,d = 0;
        for(int i = 3; i <= n; i++){              
            d = a + b + c;
            //滚动操作
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
}

滚动数组的方法

五、没看视频自己写的代码

很简单，创建一个数组，只需要 for循环赋值，并最终返回第n个数组元素就行了 注意事项： 由于数组前三个数是自己赋值的。若 n = 0 或 n = 1 的时候，数组长度很短，若不加 if 条件会导致数组越界。

class Solution {
    public int tribonacci(int n) {
        int[] arr = new int[n+1];
        arr[0] = 0;
        if(n >= 1){
            arr[1] = 1;
        }
        if(n >= 2){
            arr[2] = 1;
        }
        for(int i = 3; i <= n; i++){
                                      
            arr[i] = arr[i-1] + arr[i-2] +arr[i-3];
        }
        return arr[n];
    }
}