746. 使用最小花費爬樓梯
陣列的每個索引作為一個階梯，第 i個階梯對應著一個非負數的體力花費值 costi，
每當你爬上一個階梯你都要花費對應的體力花費值，然后你可以選擇繼續爬一個階梯或者爬兩個階梯，
您需要找到達到樓層頂部的最低花費，在開始時，你可以選擇從索引為 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，
注意：
cost 的長度將會在 [2, 1000]，
每一個 cost[i] 將會是一個Integer型別，范圍為 [0, 999]，
本題主要難在理解題意，因為題目說的太含糊不清，讓我以為是開始在第一個樓梯當起點，就得先花費它的力氣，然后去下一個樓梯上，還得花費與之對應的力氣，
因此我在本來樓梯的基礎上又加了 兩個樓梯，一個加在最下面，一個加在最上面，他們消耗的力氣都是0，然后以此為基準對cost和原先構思的基本dp進行擴充，
但其實原來cost給的是邁出該階樓梯所需要的力氣,本以為是邁入該階樓梯所需要的力氣，
理解題意后即：**
“每次你可以往前跳躍一個或者兩個，當你跳躍的時候，你會花費掉你當前位的體力”
**，所以可列出dp方程：
(i為樓梯下標，dp為花費的力氣求和)
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
老規矩
法一：動態規劃
inline int min(int x,int y)//使用行內函式增加效率
{
return x<y?x:y;
}
int minCostClimbingStairs(int* cost, int costSize){
int dp[costSize+1];//因為實際的樓梯要多一節
dp[0]=0;//理解好題意，剛開始在自己選的起點，所以不用力氣
dp[1]=0;//當走向下一步時才會需要消耗自己在這個對應階梯下標的力氣
for(int i=2;i<=costSize;i++)
{
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[costSize];
}
法二：動態規劃加滾動陣列
以空間換取時間
inline int min(int x,int y)
{
return x<y?x:y;
}
int minCostClimbingStairs(int* cost, int costSize){
int first,second;
first=0;
second=0;
for(int i=2;i<=costSize;i++)
{
int temp = second;
second=min(second+cost[i-1],first+cost[i-2]);
first=temp;
}
return second;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240130.html
標籤：其他