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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param cost int整型一维数组 
 * @param costLen int cost数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#define MIN(x,y) x<y?x:y
static int min = 0x7fffffff;
void solu(int* cost, int costLen,int step,int cost_total);
int solu2(int* cost, int costLen,int step);

int minCostClimbingStairs(int* cost, int costLen ) {
    //solu
    // write code here
//     solu(cost,costLen,0,0);
//     solu(cost,costLen,1,0);
//     return min;

    // solu2
//     int c = solu2(cost, costLen,costLen);
//     return c;
    // solu3
    int dp[100001];   // 爬到当前台阶需要的最小费用
    dp[0] = 0;        
    dp[1] = 0; 
    if(costLen==1)
        return cost[0];
    for(int i=2;i<=costLen;i++){
        dp[i] = MIN(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
    }
    return dp[costLen];
}

// void solu(int* cost, int costLen,int step,int cost_total){
//     if(step==costLen){
//         if(cost_total<min)
//             min = cost_total;
//     }
//     else{
//         cost_total+=cost[step];
//         if(costLen-step>=2)
//             solu(cost, costLen,step+2,cost_total);
//         solu(cost, costLen,step+1,cost_total);
        
//     }
    
// }


// int solu2(int* cost, int costLen,int step){
//     if(step==1 || step==0) // 不需要下面的台阶现上跳了，因此返回0
//         return 0;
//     else{
//         return MIN(solu2(cost, costLen,step-1)+cost[step-1],
//                    solu2(cost, costLen,step-2)+cost[step-2]);
//     }
// }