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

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

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

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

示例1

输入： 
[2,5,20]
复制
返回值： 
5
复制
说明： 
你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5

示例2

输入： 
[1,100,1,1,1,90,1,1,80,1]
复制
返回值： 
6
复制
说明： 
你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
			

				总花费为 6 。
			


			

				通过理解题意我们可以知道，costLen是我们要爬台阶的个数，需要到达楼梯顶部，而并不是costLen-1
			


			

				那么首先，我们先来看递归解：
			


			

				
				

					
					

						
					


					

						int minCostClimbingStairs(int* cost, int costLen ) {
					


					

						    // write code here
					


					

						     //N=n-1+(n-1);
					


					

						     //N=n-2+(n-2);
					


					

						     if(costLen==1) return cost[0]; 
					


					

						     if(costLen==2) return (cost[0]>cost[1])?cost[1]:cost[0];
					


					

						     if(costLen==3) return ((cost[0]+cost[2])>cost[1])?cost[1]:(cost[0]+cost[2]);
					


					

						     int count=costLen;
					


					

						     count-=1;
					


					

						    if((minCostClimbingStairs(cost,count)+cost[count])>(minCostClimbingStairs(cost,count-1)+cost[count-1]))
					


					

						    return minCostClimbingStairs(cost,count-1)+cost[count-1];
					


					

						    else return minCostClimbingStairs(cost,count)+cost[count];
					


					

						}
					


					

						递归：这里我们为什么要专门写出costLen==3的情况呢？我们来看例1，

[2,5,20]
在这里，显然，并不满足我们的递归规律，因此，我们需要将其列出，但是递归因时间复杂度大无法通过，因此，我们用数组来描述这一过程：
						

							
							

								int minCostClimbingStairs(int* cost, int costLen ) {
							


							

								    // write code here
							


							

								     //N=n-1+(n-1);
							


							

								     //N=n-2+(n-2);
							


							

								    int min[costLen];
							


							

								    int i=0;
							


							

								    for(i=0;i<costLen;i++)
							


							

								    {
							


							

								      if(i==0) min[0]=cost[0];
							


							

								     else if(i==1) min[1]=(cost[0]>cost[1])?cost[1]:cost[0];
							


							

								     else if(i==2) min[2]=((cost[0]+cost[2])>cost[1])?cost[1]:(cost[0]+cost[2]);
							


							

								     else min[i]=((min[i-1]+cost[i])>(cost[i-1]+min[i-2]))?(cost[i-1]+min[i-2]):(min[i-1]+cost[i]); 
							


							

								    }
							


							

								    return min[costLen-1];
							


							

								}