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

day38【代码随想录】动态规划之斐波那契数、爬楼梯、使用最小花费爬楼梯

news 来源：原创 2024/11/28 18:40:59

文章目录

前言
一、斐波那契数（力扣509）
二、爬楼梯（力扣70）
三、使用最小花费爬楼梯（力扣746）
总结

前言

1、斐波那契数
2、爬楼梯
3、使用最小花费爬楼梯

一、斐波那契数（力扣509）

在这里插入图片描述

思路：
五部曲：
1、dp数组：
dp[i]：第i个斐波那契数值为dp[i]
2、初始化
dp[0] = 1 dp[1] = 1
3、递推公式
dp[i] = dp[i-1] + dp[i-2]
4、遍历顺序
从前向后
5、打印检查

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;             
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++){
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }
}

在这里插入图片描述
补充：
类似题目：第 N 个泰波那契数（力扣1137）

二、爬楼梯（力扣70）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
在这里插入图片描述
思路：
n=1 时，也就是只有一阶楼梯时只有一种方法
n=2时，也就是有两阶楼梯时，有两种方法。
五部曲：
1、dp数组：
dp[i]：上第i+1个台阶的方式有dp[i]种
2、初始化
dp[0] = 1 //一阶楼梯
dp[1] = 2 //二阶楼梯
3、递推公式
dp[i] = dp[i-1] + dp[i-2]
4、遍历顺序
从前向后
5、打印检查

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n];
        dp[0]=1;

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

优化
在初始化时，可以让dp[0] = 1; dp[1] = 1;
这样就可以使下标与台阶数对应，并且也满足递推公式
在这里插入图片描述

三、使用最小花费爬楼梯（力扣746）

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费
在这里插入图片描述
思路：
五部曲：
1、dp数组：
dp[i]：上第i个台阶的最低花费
2、初始化
//上楼梯可以选择从0开始也可以选择从1开始
dp[0] = cost[0]
dp[1] = cost[1]
dp[2] = min(dp[0]+cost[2], dp[1]+cost[2]) 或者
dp[2] = min(dp[0],dp[1])+cost[2];
3、递推公式
dp[i] = min(dp[i-1],dp[i-2])+cost[i];
4、遍历顺序
从前向后
5、打印检查

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        //最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}

或者：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length+1];
        int[] newCost = new int[cost.length+1];
        for(int i=0;i<cost.length;i++){
            newCost[i] = cost[i]; 
        }
        newCost[cost.length] = 0;
        dp[0] = newCost[0];
        dp[1] = newCost[1];
        for(int i=2;i<=cost.length;i++){
            dp[i]=Math.min(dp[i-1],dp[i-2])+newCost[i];
        }
        return dp[cost.length];
    }
}