leetcode-746-Min Cost Climbing Stairs（动态规划）
leetcode-746-Min Cost Climbing Stairs（动态规划）
题目描述：
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].Note:
costwill have a length in the range[2, 1000].- Every
cost[i]will be an integer in the range[0, 999].
要完成的函数：
int minCostClimbingStairs(vector<int>& cost)
说明：
1、给定一个vector，里面存放着从各个阶梯“跃起”的代价，每次跃起可以跃起一个台阶，也可以一次性跃起两个台阶。比如[1,100,1,1,1,100,1,1,100,1]第一个元素1，表示从第一个阶梯跃起，到达第二个台阶，或者第三个台阶，的代价都是1。要求一直攀爬楼梯，直到到达vector之外，比如上面给的例子，一共10个台阶，那就要攀爬到第11级，到达vector之外，输出所花费的最小代价。这道题限制攀爬楼梯可以从第一个台阶开始，也可以从第二个台阶开始。
2、上述题目是不是略微嗅到了一点动态规划的味道，不需要找出全部可能的攀爬序列，只需要每次存储一个状态，然后攀爬到下一个台阶存储另一个状态。
不过这道题由于可以跃升一个台阶，也可以一次性跃升两个台阶，所以我们需要存储两个值，比如一个是到达第三个台阶的最小花费，另一个是到达第四个台阶的最小花费，接着我们就可以计算到达第五个台阶和第六个台阶的最小花费，一直这样计算下去。
代码如下：
int minCostClimbingStairs(vector<int>& cost)
{
//先计算从第一个台阶开始攀爬的情况
int i=1,j=2,s1=cost.size();//i和j表示当前到达的台阶，i在前，j在后
int costi=cost[0],costj=cost[0],total,totalnew;
//costi表示攀爬到i这一位需要的最小花费，costj同理
while(j!=s1-1&&j!=s1-2)
{
costi=min(costi+cost[i],costj+cost[j]);//计算到达i+2位的最小花费
i+=2;
costj=min(costi+cost[i],costj+cost[j]);//计算到达j+2位的最小花费
j+=2;
}
if(j==s1-2)//如果j之后还有一个元素
{
costj=costj+cost[j];
costi=costi+cost[i]+cost[i+2];
total=min(costi,costj);
}
else
{//如果j已经是最后一位
costi=costi+cost[i];
costj=costj+cost[j];
total=min(costi,costj);
}
//计算从第二个台阶开始攀爬的情况，下述代码同理
i=2,j=3;
costi=cost[1],costj=cost[1];
while(j!=s1-1&&j!=s1-2)
{
costi=min(costi+cost[i],costj+cost[j]);
i+=2;
costj=min(costi+cost[i],costj+cost[j]);
j+=2;
}
if(j==s1-2)
{
costj=costj+cost[j];
costi=costi+cost[i]+cost[i+2];
totalnew=min(costi,costj);
}
else
{
costi=costi+cost[i];
costj=costj+cost[j];
totalnew=min(costi,costj);
}
return min(total,totalnew);
}上述代码实测14ms，beats 49.37% of cpp submissions。
3、改进：
可以从第一个台阶开始，也可以从第二个台阶开始，笔者隐隐觉得这种情况，和我们每一步要处理的两个最小花费，有相似的地方。
于是，我们可以把从第二个台阶开始的情况，也纳入处理的范畴，一起处理，这样可以快很多，代码如下：（附解释，主要修改了costj的初始值）
int minCostClimbingStairs(vector<int>& cost)
{
int i=1,j=2,s1=cost.size();
int costi=0,costj=min(costi+cost[i],cost[0]),total;
//costi表示到达i也就是第二个台阶（i从0开始）的最小花费，当前为0
//costj表示到达j也就是第三个台阶（j从0开始）的最小花费，考虑从
//第一个台阶开始攀爬和从第二个台阶开始攀爬的两种情况
while(j!=s1-1&&j!=s1-2)
{
costi=min(costi+cost[i],costj+cost[j]);
i+=2;
costj=min(costi+cost[i],costj+cost[j]);
j+=2;
}
if(j==s1-2)//把2中未改进的代码简化一下
total=min(costi+cost[i]+cost[i+2],costj+cost[j]);
else
total=min(costi+cost[i],costj+cost[j]);
return total;
}上述代码实测12ms，beats 93.11% of cpp submissions。