首页 > 试题广场 >

最小花费爬楼梯

[编程题]最小花费爬楼梯
  • 热度指数：74574 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个整数数组 ，其中 是从楼梯第个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 ，数组中的值满足
示例1

输入

[2,5,20]

输出

5

说明

你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5
示例2

输入

[1,100,1,1,1,90,1,1,80,1]

输出

6

说明

你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
算法知识视频讲解
添加回答
C
牛客322847027号头像 牛客322847027号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param cost int整型一维数组
 * @param costLen int cost数组长度
 * @return int整型
 */
 #include<string.h>
int minCost(int cost1,int cost2){ //定义一个比较函数，选较小值
    if(cost1>cost2)
        return  cost2;
    else
        return cost1;
}
int minCostClimbingStairs(int* cost, int costLen ) {
    if(costLen==1){
        return cost[costLen-1];//楼层为1层，则只能从第0层爬上去；不能默认为直接在第1层
    }
    if(costLen==2){
        return cost[0]>cost[1]?cost[1]:cost[0];//楼层为2，比较第0层爬还是第1层爬代价小
    }
    int dp[costLen];  //定义dp数组，dp[i]表示到达第i层的最小代价
    dp[0]=cost[0];      //运行到这时至少楼层为3
    dp[1]=cost[1];
    for(int i=2;i<costLen;i++){
        dp[i]=minCost(dp[i-1]+cost[i], dp[i-2]+cost[i]);
    }
    return dp[costLen-1] < dp[costLen-2]  ? dp[costLen-1] : dp[costLen-2];

}
发表于 2025-02-27 20:50:10 回复(0)
C
何处明月楼头像 何处明月楼
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param cost int整型一维数组
 * @param costLen int cost数组长度
 * @return int整型
 */
#include <stdio.h>
int minCost(int number1,int number2)
{
    if (number1<number2)
    {
        return number1;
    }
    else
    {
         return number2;
    }
}

int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    if (costLen==1)
    {
        return cost[costLen-1];
    }
    else
    {
        int dp[costLen];
       
        //考虑是第一步是走一步还是两步
        dp[0]=cost[0];

        dp[1]=cost[1];

        for (int i=2;i<costLen;i++)
        {
            //考虑到i所需要的金币数

            //首先考虑走i
            //dp[i]=minCost(dp[i-1],dp[i-2])+cost[i]

            //然后考虑不走i
            //dp[i]=dp[i-1]+cost[i+1]

            dp[i]=minCost(minCost(dp[i-1],dp[i-2])+cost[i],dp[i-1]+cost[i+1]);
            printf("%d",dp[i]);
        }

        //最后直接返回到最后一个需要花费的金币数
        return dp[costLen-1];
    }
} 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param cost int整型一维数组
 * @param costLen int cost数组长度
 * @return int整型
 */
#include <stdio.h>
int minCost(int number1,int number2)
{
    if (number1<number2)
    {
        return number1;
    }
    else 
    {
         return number2;
    }
}

int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    if (costLen==1)
    {
        return cost[costLen-1];
    }
    else 
    {
        int dp[costLen];
       
        //考虑是第一步是走一步还是两步
        dp[0]=cost[0];

        dp[1]=cost[1];

        for (int i=2;i<costLen;i++)
        {
            //考虑到i所需要的金币数

            //首先考虑走i
            //dp[i]=minCost(dp[i-1],dp[i-2])+cost[i]

            //然后考虑不走i
            //dp[i]=dp[i-1]+cost[i+1]

            dp[i]=minCost(minCost(dp[i-1],dp[i-2])+cost[i],dp[i-1]+cost[i+1]);
            printf("%d",dp[i]);
        }

        //最后直接返回到最后一个需要花费的金币数
        return dp[costLen-1];
    }
}

发表于 2024-12-04 09:31:53 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
#define min(a,b)   (a>b ? b : a)
int minCostClimbingStairs(int* cost, int costLen ) {
    int res[100001], i;
    res[0] = 0;
    res[1] = 0;
    for(i=2; i<=costLen; i++)
    res[i] = min(res[i-1]+cost[i-1], res[i-2]+cost[i-2]);
    return res[costLen];
}

编辑于 2024-03-23 22:53:44 回复(0)
C
周香华头像 周香华
#include <math.h>
int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    int dp[costLen];
    dp[0]=0;dp[1]=0;
    for(int i=2;i<=costLen;i++)
    {
        dp[2]=fmin(dp[0]+cost[i-2],dp[1]+cost[i-1]);
        dp[0]=dp[1];
        dp[1]=dp[2];
    }
    return dp[2];

}
发表于 2023-10-14 20:12:07 回复(0)
C
飞天马里奥头像 飞天马里奥 
int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    // int ret = 0;

    int dp[costLen];

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

    for(int i = 2; i <= costLen; i++){
        dp[i] = (dp[i - 1] + cost[i - 1]) > (dp[i - 2] + cost[i - 2]) ? (dp[i - 2] + cost[i - 2]) : (dp[i - 1] + cost[i - 1]);
        
    }
    return dp[costLen];
}


发表于 2023-02-23 17:13:36 回复(1)
C
JayneChou头像 JayneChou 
#include <math.h>
#include <stdlib.h>
int minCostClimbingStairs(int* cost, int costLen ) {
    int *minCost = (int*)malloc(sizeof(int) * (costLen + 1));
    minCost[0] = 0, minCost[1] = 0;//在clion里默认初始化为0，这里没有害我浪费半个小时
    for(int i = 2; i <= costLen; i++){
        minCost[i] = (int)fmin(cost[i - 1] + minCost[i - 1], cost[i - 2] + minCost[i - 2]);
    }
    return minCost[costLen];
}

发表于 2023-02-18 16:34:31 回复(0)
C
cloudyshun头像 cloudyshun
int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    if (costLen == 1){
        return 0;
    }
    int fei[costLen + 1];
    fei[0] = fei[1] = 0;
    for(int i = 2; i < costLen + 1; i++){
        if((fei[i-2] + cost[i-2]) < (fei[i-1] + cost[i-1])){
            fei[i] = (fei[i-2] + cost[i-2]);
        }else{
            fei[i] = (fei[i-1] + cost[i-1]);
        }
    }
    return fei[costLen];
}
发表于 2023-01-01 14:13:25 回复(0)
C
牛客42558553号头像 牛客42558553号 
int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    if(costLen==1||costLen ==0)
    {
        return 0;
    }
    int count1 = minCostClimbingStairs(cost,costLen-1) + cost[costLen-1];
    int count2 = minCostClimbingStairs(cost,costLen-2) + cost[costLen-2];
    return count1<count2?count1:count2;
}
一开始用C++写发现时间超了，以为这道题只能用C写，用C写发现时间也超了，官方就完全不给活路呗。
发表于 2022-12-27 17:52:34 回复(0)
C
牛客579577851号头像 牛客579577851号
//从第n-1或n-2层开始往前推
//n-1 或 n-2至终点的最小花费是已知的 
int Method3(int cost[],int start , const int end){  //动态规划 
    int cost1 = cost[end - 2];
    int cost2 = cost[end - 1];
    int t;
    //cost1 始终在cost2之前
    for(int round = end - 3;round >= 0;round--){
        t = cost1;
        cost1 = cost[round] + ((cost1 > cost2)?cost2 : cost1);
        cost2 = t;
    }
    return cost1<cost2?cost1:cost2;//选较小值
}
int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    return Method3(cost, 0, costLen);
}
发表于 2022-12-13 13:02:58 回复(0)
C
夕木月头像 夕木月
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param cost int整型一维数组 
 * @param costLen int cost数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
//这个递归会超时
int recost(int* cost, int rellycostLen )
{
    if(rellycostLen == 2)
        return 0;
        //return cost[0];
    if(rellycostLen == 3)
        return (cost[0] < cost[1]) ? cost[0] : cost[1];
    
    int a = 0;
    int b = 0; 
    int c = 0;
    for(int i = 3;i <= rellycostLen;i++)//这种就不会超时
    {
        c = a+cost[i-3] < b+cost[i-2] ? a+cost[i-3] : b+cost[i-2] ;
        a = b;
        b = c;
        
    }
    return c;
    
    //下面这个递归会超时
    //return (recost(cost,rellycostLen-1)+cost[rellycostLen-2] < recost(cost,rellycostLen-2)+cost[rellycostLen-3] ) ?
       // recost(cost,rellycostLen-1)+cost[rellycostLen-2] : recost(cost,rellycostLen-2)+cost[rellycostLen-3];
}

int minCostClimbingStairs(int* cost, int costLen )
{
    // write code here
    if(costLen == 1)
        return 0;
    if(costLen == 2)
        return (cost[0] < cost[1]) ? cost[0] : cost[1];
    
    return recost(cost,costLen+1);
}
发表于 2022-07-28 16:19:02 回复(1)
C
taishan头像 taishan
这一题运用动态规划的基本思想就是
我们上第一和第二阶台阶的最小费用都为0，可以直接从地面跳上去；
我们上第三阶台阶的最小费用，取决于上第一和第第二阶台阶的最小费用；
同理，我们上第n阶的最小费用，就取决于上第n-1阶台阶费用+cost【n-1】和上第n-2阶台阶的费用+cost[n-2]；
值得注意的是我们要上的是楼顶，楼梯总共有n阶，所以我们要求上n+1阶台阶的最小费用。
int minCostClimbingStairs(int* cost, int costLen ) {
    // write code here
    if(costLen>2)
    {
        int min=0;
        int min1=0;
        int min2=0;
        int a[costLen];
        int i;
        for(i=2;i<=costLen;i++)
        {
            if((min1+cost[i-2])<(min2+cost[i-1]))
                min=min1+cost[i-2];
            else
                min=min2+cost[i-1];
            min1=min2;
            min2=min;
        }
        return min;
    }
    else
        return 0;
}
发表于 2022-07-14 21:13:17 回复(0)
提交观点

问题信息

动态规划
难度：
13条回答 3896浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最小花费爬楼梯

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号