前言
水题、动规（异形种巨人爬楼梯）
正文
问题来源
本问题来自leetcode上的746题。这道题并不难（定主基调）
问题描述
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i]。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
分析：
由于爬行楼梯的时候，最后一步时可以从倒数第二阶楼梯直接上楼。这道题并不是返回形如dp[size-1]，而是返回min(dp[size-2],dp[size-1])。
C代码如下：
#define min(x,y) ((x)<(y)?(x) : (y))
int minCostClimbingStairs(int* cost, int costSize) {
int *dp = NULL;
int ret;
int i;
int temp;
dp = (int*)malloc(sizeof(int)*costSize);
dp[0] = cost[0];
dp[1] = cost[1];
for(i=2;i<costSize;i++)
{
dp[i] = min(dp[i-1],dp[i-2])+cost[i];
}
ret = min(dp[costSize-2],dp[costSize-1]);
free(dp);
dp = NULL;
return ret;
}
优化空间复杂度
int minCostClimbingStairs(int* cost, int costSize) {
int c1 = 0;
int c2 = 0;
for (int i = 0; i < costSize; i++){
int t = c1;
c1 = cost[i] + (c1 < c2 ? c1 : c2);
c2 = t;
}
return c1 < c2 ? c1 : c2;
}
总结：
别陷入返回定式思维。
结语
闲来无事的话，多练习练习，做做题。
