本文共 1963 字，大约阅读时间需要 6 分钟。
你需要爬上一个N层的楼梯,在爬楼梯过程中,每阶楼梯需花费非负代价,第i阶楼梯花费代价表示为cost[i],一旦你付出了代价,你可以在该阶基础上往上爬一阶或两阶。你可以从第0阶或者第1阶开始,请找到到达顶层的最小的代价是多少
N和cost[i]皆为整数,且N∈[2,1000],cost[i]∈[0,999]
输入为一行整数,对应cost数组
输出一个整数,表示花费的最小代价
1 100 1 1 1 100 1 1 100 1
6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
10 15 20
15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
例如样例1：1 100 1 1 1 100 1 1 100 1
dp[0]和dp[1]是可以直接出发的点，所以在他们之前的最少花费为0.
dp[0]=0 dp[1]=0 ;
dp[2]中要存储到达0和1中最少的花费：dp[0]+cost[0]=0+1=1, dp[1]+cost[1]=0+100=100, 所以dp[2]=1;
dp[3]中要存储到达1和2中最少的花费：dp[1]+cost[1]=0+100=100, dp[2]+cost[2]=1+1=2, 所以dp[3]=2;
dp[4]中要存储到达2和3中最少的花费：dp[2]+cost[2]=1+1=2, dp[3]+cost[3]=2+1=3, 所以dp[4]=2;
dp[5]中要存储到达3和4中最少的花费：dp[3]+cost[3]=2+1=3, dp[4]+cost[4]=2+1=3, 所以dp[5]=3;
dp[6]中要存储到达4和5中最少的花费：dp[4]+cost[4]=2+1=3, dp[5]+cost[5]=3+100=103, 所以dp[6]=3;
dp[7]中要存储到达5和6中最少的花费：dp[5]+cost[5]=3+100=103, dp[6]+cost[6]=3+1=4, 所以dp[7]=4;
dp[8]中要存储到达6和7中最少的花费：dp[6]+cost[6]=3+1=4, dp[7]+cost[7]=4+1=5, 所以dp[8]=4;
dp[9]中要存储到达7和8中最少的花费：dp[7]+cost[7]=4+1=5, dp[8]+cost[8]=4+100=104, 所以dp[9]=5;
dp[10]中要存储到达8和9中最少的花费：dp[8]+cost[8]=4+100=104, , dp[9]+cost[9]=5+1=6, 所以dp[10]=6;
class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp=new int[10000]; dp[0]=0; dp[1]=0; for(int i=2;i dp[0]最低花费即为cost[0] , dp[1]最低花费即为cost[1].
dp[0]=1, dp[1]=100
dp[2] = dp[0]和dp[1]中的最低花费 + cost[2] = dp[0]+1=2
dp[3] = dp[1]和dp[2]中的最低花费 + cost[3] = dp[2]+1=3
dp[4] = dp[2]和dp[3]中的最低花费 + cost[4] = dp[2]+1=3
dp[5] = dp[3]和dp[4]中的最低花费 + cost[5] = dp[3]+100=dp[4]+100=103
dp[6] = dp[4]和dp[5]中的最低花费 + cost[6] = dp[4]+1=4
dp[7] = dp[5]和dp[6]中的最低花费 + cost[7] = dp[6]+1=5
dp[8] = dp[6]和dp[7]中的最低花费 + cost[8] = dp[6]+100=104
dp[9] = dp[7]和dp[8]中的最低花费 + cost[9] = dp[7]+1=6
class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp=new int[10000]; dp[0]=cost[0]; dp[1]=cost[1]; for(int i=2;i
转载地址：http://sszci.baihongyu.com/