DP4 最小花费爬楼梯

喜欢ヅ旅行 2023-10-01 01:00 36阅读 0赞

描述  
给定一个整数数组 cost \\cost ，其中 cost\[i\]\\cost\[i\] 是从楼梯第i \\i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 1 \\le n \\le 10^5 \\1≤n≤10  
5  
，数组中的值满足 1 \\le cost\_i \\le 10^4 \\1≤cost  
i  
  
≤10  
4

输入描述：  
第一行输入一个正整数 n ，表示数组 cost 的长度。  
第二行输入 n 个正整数，表示数组 cost 的值。  
输出描述：  
输出最低花费  
示例1  
输入：  
3  
2 5 20  
复制  
输出：  
5  
复制  
说明：  
你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5  
示例2  
输入：  
10  
1 100 1 1 1 90 1 1 80 1  
复制  
输出：  
6  
复制  
说明：

你将从下标为 0 的台阶开始。  
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。  
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。  
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。  
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。  
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。  
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。  
总花费为 6 。

#include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    using namespace std;
    int main()
    {
        
    	int n;
    	cin >> n;//10
    	vector<int> dt(n);
    
    	for (int i = 0;i < n;i++)
    		cin >> dt[i];
    		//1 100 1 1 1 90 1 1 80 1
    		
    	vector<int> cost(n);
    	
    	cost[0] = 0;cost[1] = 0;
    	
    	for (int i = 2;i < n;i++){
        
    		cost[i] = min(dt[i - 1] + cost[i - 1],dt[i - 2] + cost[i - 2]);//从0或1开始
    		//cost[2]=dt[0] + cost[0]=1+0=1  ;;;dt[i - 2] + cost[i - 2]
    		//cost[3]=dt[2] + cost[2]=1+1=2  ;;;dt[i - 1] + cost[i - 1]
    		//cost[4]=dt[2] + cost[2]=1+1=2  ;;;dt[i - 2] + cost[i - 2]
    		//cost[5]=dt[4] + cost[4]=1+2=3  ;;;dt[i - 1] + cost[i - 1]
    		//cost[6]=dt[4] + cost[4]=1+2=3  ;;;dt[i - 2] + cost[i - 2]
    		//cost[7]=dt[6] + cost[6]=1+3=4  ;;;dt[i - 2] + cost[i - 2]
    		//cost[8]=dt[7] + cost[7]=1+4=5  ;;;dt[i - 1] + cost[i - 1]
    		//cost[9]=dt[8] + cost[8]=1+5=5  ;;;dt[i - 1] + cost[i - 1]
    	
    	}
    	int mincost=min(cost[n - 1] + dt[n - 1],cost[n - 2] + dt[n - 2]);
    	//cost[n - 1] + dt[n - 1],cost[n - 2] + dt[n - 2]=cost[9]+dt[9],cost[8]+dt[8]
    	//cost[9]+dt[9]=5+1=6
    	
    	cout << mincost;
    	
    	return 0;
    }