TOP101题解 | BM64#最小花费爬楼梯#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.29
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 创建一个costLen + 1 大小的数组dp;
 *          循环遍历数组,dp[i]表示跳到第i级台阶最小的过路费
 *              遍历结束,倒数第一、倒是第二级台阶最小的就是整体的最小的花费
 * @param cost int整型一维数组 
 * @param costLen int cost数组长度
 * @return int整型
 */

#include <math.h>
#include <stdlib.h>

int minCostClimbingStairs(int* cost, int costLen ) 
{
    // write code here
    if(0 == costLen)
    {
        return 0;//0级台阶无过路费
    }
    else if (1 == costLen) 
    {
        return cost[0];//1级台阶的过路费
    }
    else //2级以上
    {
        int* dp = (int*)malloc((costLen + 1) * sizeof(int));
        dp[0] = cost[0];
        dp[1] = cost[1];

        for(int i = 2; i < costLen; i++)
        {
            /*对于第i级,需要从第i级的前一两级跳上来，并且跳上第i级会立马产生过路费
            最小费用就是:第i级的过路费+前两级最小的过路费跳到本级*/
            dp[i] = cost[i] + fmin(dp[i - 1], dp[i - 2]);
        }
        int result = fmin(dp[costLen - 1], dp[costLen - 2]);

        free(dp);

        return result;
    }

}