DP4 最小花费爬楼梯

本文主要是介绍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;
}

这篇关于DP4 最小花费爬楼梯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---