2023.12.17力扣每日一题

2023-12-18 20:35:38

题目来源

力扣每日一题;题序:746

我的题解

方法一 动态规划(无优化)

这是一道比较典型的动态规划题。首先动态初态:选择下标0或者1作为初始阶梯,即dp[0]=dp[1]=0;
2<=i<=n时,dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

时间复杂度:O(n)
空间复杂度:O(n)。需要额外的dp表

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

    }
}
方法二 动态规划(空间优化)

在方法一中,发现当前状态只于上两个状态相关,因此使用两个变量实现滚动数组来进行空间优化

时间复杂度:O(n)
空间复杂度:O(1)

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n=cost.length;
        if(n==2){
            return Math.min(cost[0],cost[1]);
        }
        int dp_0=cost[0];
        int dp_1=cost[1];
        for(int i=2;i<=n;i++){
            int t=dp_0;
            if(i==n){
                dp_0=dp_1;
                dp_1=Math.min(t,dp_1);
            }
            else{
                dp_0=dp_1;
                dp_1=Math.min(t,dp_1)+cost[i];
            }
        }
        return dp_1;
    }
}

昨天困难我唯唯诺诺,今天简单我重拳出击😄

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

文章来源:https://blog.csdn.net/weixin_42075274/article/details/135069559
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。