当前位置：首页 > article >正文

【Leetcode】动态规划：从经典例题剖析解题精要

article 2025/2/26 9:33:15

前言

🌟🌟本期讲解关于力扣的几篇题解的详细介绍~~~

🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客

🔥 你的点赞就是小编不断更新的最大动力

🎆那么废话不多说直接开整吧~~

📚️1.第N个泰波那契数

🚀1.1题目解析

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

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

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

例如：

输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

可以看到要求出某一个值，那么就要将前面所有的值计算出来，很明显这种就涉及到动态规划的思想；

🚀1.2算法思想

所谓的动态规划就是五部法，如下所示：

1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值

第一：状态表示
一般创建一个一维数组，这里我们一般用dp来进行表示，填满里面某个值的结果，例如这里我们的dp[i] 就可以表示第i个泰波那契数

第二：状态转移方程

这里的状态转移方程是指：在计算某一个位置的值时，需要用到前一个值，但是前一个值需要用到前前一个值，这里的规律我们就可以使用一个方程来进行表示；

这里的题目中的Tn+3 = Tn + Tn+1 + Tn+2，我们就可以用dp表来进行方程的转化：

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

第三：初始化

这里初始化的本质目的就是在防止在方程中某个值越界，例如dp [ i - 3 ]这里假如下标 i 为2或者0，1那么此时就会导致越界问题，那么这里就要进行初始化：

T0 = 0, T1 = 1, T2 = 1

对应的dp表那么就是：dp[ 0 ] = 0 , dp[ 1 ] = 1, dp[ 2 ] = 1

第四：填表顺

这里很明显是从左往右一次填表，那么这里小编就不再过多解释了

第五：返回值

在填完dp表后，根据题目要求返回对应下标的值即可

🚀1.3题目代码

代码如下所示：

class Solution {
    public int tribonacci(int n) {
        //dp表
        int[] dp = new int[n+1];
        if(n == 0)return 0;
        if(n == 1 || n==2)return 1;
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

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

注意：当然这里还要进行额外的条件判断，即n = 0 n = 1 n = 2时对应的返回的泰波那契数

本题是动态规划较为容易的题目，最主要的还是学习种类的解决动态规划这类题目的思想，即解决动态规划的五部操作；

📚️2.最小花费爬楼梯

🚀2.1题目解析

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

例如：

cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

大致就是一次走一步或者两步，但是都要付出对应下标的体力值，那么接下来小编就进行题目的分析了；

🚀2.2算法思想

这里咋一看，感觉按照上述的五步走来看，这里的方程是如何实现的呢？

种类的状态表示根具题目可以是：到达某个位置的最小花费，但是如何确定最小花费呢？

分析如下图所示：

这里由于dp表存储的都是最小值，那么在计算某一个位置的时候，只需要考虑前一步，或者前两步的对应消耗体力值，所以，这里就要取最小花费体力的下标到达目标位置

这里还要进行初始化，dp[ 0 ],dp[ 1 ] ;

例如：

dp[ 0 ] = 0 到达下标为0的位置需要的最小花费，这里题目说可以直接在这里

dp[ 1 ] = 0和上述同理

dp[ 2 ] 这里就是关键了，这里位置可以由0下标两步到达，或者1下标一步到达，所以要进行比较，这里两个值最小花费并且加上从这里到达2下标位置的所消耗的体力值；

所以状态表示方程就是：

dp[ i ] = Math.min((dp[ i -1 ] + cost [ i - 1]),(dp [ i - 2] + cost [ i - 2 ]))

解释：由于dp表示到达这个位置最小值，所以只需要管理到达目标位置的两种方式，比较两种方式所消耗的体力以及之前到达这两个位置所消耗的最小值即可；

🚀2.3题目代码

代码如下：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];

        dp[0] = 0;dp[1] = 0;

        for(int i = 2;i < dp.length ;i++){
            dp[i] = Math.min((dp[i-1]+cost[i-1]),(dp[i-2]+cost[i-2]));
        }

        return dp[n];
    }
}

注意：当然这里还要考虑边界的问题，以及爬到楼梯最顶端指的就是数组长度的下标的位置，所以这里的一维数组的长度是n+1;