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

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阶的代价。

算法介绍

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

算法步骤

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

算法分析

• 时间复杂度：O(n)，其中n是数组cost的长度。我们只需要遍历数组一次。
• 空间复杂度：O(n)，因为使用了额外的数组空间。
• 易错点：
  • 确保正确初始化dp数组。
  • 在计算状态转移时，确保正确处理边界条件。

相似题目

请注意，以上表格仅为示例，实际链接可能需要根据具体平台和题目编号进行调整。