当前位置：首页 > article >正文

leetcode746. 使用最小花费爬楼梯，动态规划

article 2024/9/23 20:14:47

leetcode746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。

支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。

支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

在这里插入图片描述

题目分析

这是一个关于动态规划的问题。题目要求实现一个函数minCostClimbingStairs，该函数接受一个整数数组cost，并返回到达楼梯顶部的最小花费。数组的每个元素代表到达楼梯第i阶的代价。

算法介绍

为了解决这个问题，我们可以使用动态规划。动态规划的关键在于找到一个状态转移方程，用于计算到达每一阶楼梯的最小花费。

算法步骤

初始化一个长度为size+1的数组dp，用于存储到达每一阶楼梯的最小花费。
初始化dp[0]和dp[1]为0，因为起始点不需要花费。
从第2阶开始，对于每个阶数i，计算到达第i阶的最小花费，这可以通过取到达第i-1阶和第i-2阶的最小花费加上第i-1阶和第i-2阶的代价来得到。
最后，返回dp[size]，即到达楼梯顶部的最小花费。

算法流程

算法代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
    int size=cost.size();
    vector<int> dp(size+1,0);
    dp[0]=0;
    dp[1]=0;
    for(int i=2;i<=size;i++)
    {
        dp[i]=min((dp[i-1]+cost[i-1]),(dp[i-2]+cost[i-2]));
    }
    return dp[size];
    }
};