這個很明顯要用動态規劃來做,首先,我們設一個動态規劃的數組dp[n+1],其中n是樓梯數,dp[i]表示到達第i個台階的時候最小的花費。設定一個cost[n]來存儲爬某一個樓梯要用的代價。第一個樓梯的代價是cost[n-1],以此類推。
接下來列出動态轉移方程,很明顯,我們要麼在之前跨了兩級,要麼隻跨了一級。如果是跨了兩級。
dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
代碼如下所示:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> cost(n);
for(int i=0;i<n;++i){
cin>>cost[i];
}
vector<int> dp(n+1);
for(int i=2;i<=n;++i){
dp[i]=min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1]);
}
cout<<dp[n]<<endl;
return 0;
}