题解 | #最小花费爬楼梯#

DP问题五步走：

1. dp数组的含义以及下标的含义
2. 递推公式
3. 如何初始化
4. 遍历顺序
5. 打印数组

本题对前四个问题有着非常好的示范效果。

题目分析在代码里解释的应该比较详细了，不再赘述。

吐槽一下测试用例有六次方，题目里说了到五次方。

第一篇牛客题解，溜了溜了

#include<iostream>
#include<cstring>

/*
描述
给定一个整数数组 cost  ，其中 cost[i] 是从楼梯第i 个台阶向上爬需要支付的费用，下标从0开始。
一旦你支付此费用，即可选择向上爬一个或者两个台阶。
*/
using namespace std;
const int MAXN = 100000+1;
int cost[MAXN];
int dp[MAXN];

//手写分析过程：
//从大到小分析 对于第 i 阶，到顶需要的花费   dp[i] = cost[i] + min(dp[i + 1] , dp[i + 2])
//最后取 min(dp[0] , dp[1])
int main(){
	int n;
	cin>>n;
	for (int i = 0; i < n; ++i){
		cin>>cost[i];
	}
	if(n == 1){
		cout<<cost[0]<<endl;
		return 0;
	}else if(n == 2){
		cout<<min(cost[0],cost[1]);
		return 0;
	}else{
		memset(dp,0,sizeof(dp));
		//dp初始化 对于最后一阶和倒数第二阶而言，他们需要的花费就是他们位置的cost
		dp[n - 1] = cost[n - 1];
		dp[n - 2] = cost[n - 2];
		//从单数第三个开始，花费 就是 cost[i] + min(dp[i + 1] , dp[i + 2])
		//跳一步 和 跳两步 两种情况取花费少的情况
		for (int i = n - 3; i >= 0; --i){
			dp[i] = cost[i] + min(dp[i + 1],dp[i + 2]);
		}
		//最后从“从0开始”和“从1开始” 两者选小的那个
		//实际上，二者表达的是 从0 、1开始之后的能实现的最低花费已经计算出来了
		//选择只是为了选择 “从哪个开始更优”
		cout<<min(dp[0],dp[1])<<endl;
	}
	
	return 0;
}