首页 > 试题广场 >

最小花费爬楼梯

[编程题]最小花费爬楼梯

热度指数：83651 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数数组 $cost \$ ，其中 $cost[i]\$ 是从楼梯第 $i \$ 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

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

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

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ，数组中的值满足 $1 \le cost_i \le 10^4 \$

示例1

输入

[2,5,20]

输出

说明

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

示例2

输入

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

输出

说明

你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

算法知识视频讲解

牛客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)

何处明月楼

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @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)

一个优雅的程序猿

#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)

周香华

#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)

飞天马里奥

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)

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)

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)

牛客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)

牛客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)

夕木月

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)

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)