目录
C++最小花费爬楼梯
一、题目要求
1、编程实现
给定一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
注：总的台阶数n在1到40之间
2、输入输出
输入描述：第一行输入台阶个数n（1<=n<=40）
第二行输入n个数
输出描述：只有一行，一个整数，即爬到楼顶部的最低花费
输入样例：
8
2 3 2 3 2 3 1 2输出样例：
7二、算法分析
- 从给定题目的初步分析可以看出，本题同样是爬楼梯题型
- 是算法学习008的升级版，只是加了个费用的权值
- 所以可以采用动态规划的方式实现
- 由于要求的是最小费用，所以可以设置动态数组dp[i]，i表示爬上第几个台阶；所以对应的dp[i]就是爬上第i个台阶对应的最小费用
- 而要爬到第i个台阶可以从第i-1个台阶，然后往上爬1步，对应花费为爬到第i-1个台阶的最小费用（dp[i-1]）加上从第i-1个台阶网上爬的费用（cost[i-1]）
- 也可以从第i-2个台阶，然后往上爬2步，对应花费为爬到第i-2个台阶的最小费用（dp[i-2]）加上从第i-2个台阶网上爬的费用（cost[i-2]）
- 所以可以得出对应的动态数组dp[i]的状态转移方为：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
- 而题目已经告知爬楼梯的时候可以从下标为0和下标为1的台阶开始爬，所以dp[0]=dp[1]=0
三、程序编写
//程序中的dp和cost数组可以使用动态数组vector进行实现更好
#include<bits/stdc++.h>
using namespace std;
int dp[45];
int climbCost(int cost[],int n)
{
dp[0] = dp[1] = 0;
for(int i=2;i<=n;i++)
dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
return dp[n];
}
int main()
{
int n,cost[45];
memset(cost,0,sizeof(cost));
cin >> n;
for(int i=0;i<n;i++)
cin >> cost[i];
cout << climbCost(cost,n);
return 0;
}本文作者：小兔子编程 作者首页：https://blog.csdn.net/frank2102
四、运行结果
8
2 3 2 3 2 3 1 2
7五、考点分析
难度级别：一般，这题相对而言在于最小花费，具体主要考查如下：
- 分析题目，找到解题思路
- 充分掌握变量和数组的定义和使用
- 学会动态规划算法的原理和使用
- 学会输入流对象cin的使用，从键盘读入相应的数据
- 学会for循环的使用，在确定循环次数的时候推荐使用学会
- 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
- 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
- 充分掌握变量定义和使用、分支语句、循环语句和动态规划算法的应用
PS：方式方法有多种，小朋友们只要能够达到题目要求即可！