C++-leetcode题解之746. Min Cost Climbing Stairs.cpp

C++ LeetCode题解之746. Min Cost Climbing Stairs的题解是一个经典的动态规划问题。问题的核心是在一个楼梯的成本数组中，找到从底部到顶部的最小成本。这个顶部可以是最后一阶楼梯，也可以是倒数第二阶楼梯，因为你可以从任何一阶开始向上走一步或两步到达顶部。 在C++中实现这个问题的解决方案时，需要使用一个动态规划数组dp，其中dp[i]代表到达第i阶楼梯所需的最小成本。由于可以从第i-1阶或第i-2阶向上走，所以状态转移方程为：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。初始状态设置为dp[0] = cost[0]和dp[1] = cost[1]，因为到达第一阶和第二阶楼梯的成本就是各自对应的成本。 需要注意的是，这个问题的数组索引是从0开始的，而楼梯的“顶部”实际上是数组的长度，因为最后一阶楼梯的索引是数组长度减一。因此，在动态规划数组的最后添加一个额外的元素，表示到达顶部之后的额外一阶楼梯的成本，这个额外的成本为0，因为在顶部不需要再支付任何费用。 解题过程中，应确保数组的大小和边界条件被正确处理。在C++中，可以使用数组或者向量（vector）来实现动态规划数组dp。同时，空间优化也是可能的，因为计算dp[i]只用到了前两个状态，所以不需要保存整个dp数组，只需要保存前两个状态的最小成本即可。 返回dp数组的最后一个元素dp[n]，它代表到达楼梯顶部的最小成本。整个代码实现应该简洁明了，同时保证算法的时间复杂度为O(n)，空间复杂度为O(1)，如果进行了空间优化的话。