DP4 最小花费爬楼梯

原题链接：最小花费爬楼梯_牛客题霸_牛客网

目录

1. 题目描述

2. 思路分析

3. 代码实现

---

1. 题目描述

2. 思路分析

dp。

开一个dp数组和a数组。dp[i]表示在当前这一格所需要的费用，a数组其实就是题目中的cost数组。

因为最后要求到顶楼的最低费用，每次只能走一格或走两格，所以我们要求走一格到当前格的费用和走两个到当前格的费用的最小值。

在第0格和第1格时不需要费用。

初始状态： dp[0]=0  dp[1]=0

状态转移方程：dp[i]=min(dp[i-2]+a[i-2],dp[i-1]+a[i-1])

最终状态 dp[n]

3. 代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+10;
int a[N],dp[N];signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n; cin>>n;for(int i=0;i<n;i++) cin>>a[i];dp[0]=0;dp[1]=0;for(int i=2;i<=n;i++){dp[i]=min(dp[i-2]+a[i-2],dp[i-1]+a[i-1]);}cout<<dp[n]<<endl;
}