题解 | #最小花费爬楼梯#
https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7
方法一：动态规划（反向）
这道题看着和爬台阶那道很像，但是因为没有做过几道dp的题目，所以开始自己想也有点懵🤣，就像爬台阶一样，应该都是站在最高点往回想，退一步还是两步，然后再加上之前的子问题。但是台阶的问题我就想的是从前往后，因为那个从前往后和从后往前想是一样的，但是这个题目有代价了，所以整懵了。看到有题解写的和我的想法一样的，也是从前往后想，即站在此处，要到达最高阶楼梯可以怎么走？以下为题解
-
表示从下标为i的楼梯上到最高处所花费的最小代价
-
如
，即从本层可以跳一步/两步
-
为了表示是跳到最高处，所以这个
的最大值就是
中
，计算方法同上。
- 因此，为了知道从开始跳到最高处需要的最小代价，需要一直计算到起点（0或1）
-
即，最小代价 =
-
这样定义我觉得比较好理解，不同之处在于计算是要从大往小倒着计算
其实理解了怎样写都行，两个想法只是反着来了，写法是有一点不同。以下为代码：
public int minCostClimbingStairs (int[] cost) {
int n = cost.length;
int[] dp = new int[n + 2]; // 初始化dp数组长度为cost长度+2
dp[n] = dp[n + 1] = 0; // 超过cost下标的部分，dp值定义为0
for (int i = n - 1; i >= 0; i--) { // 从cost最后一个下标开始计算
dp[i] = Math.min(cost[i] + dp[i + 1], cost[i] + dp[i + 2]);
}
return Math.min(dp[0], dp[1]); // 返回从起点开始的最小代价
}
时间复杂度：O(n)，空间复杂度：O(n)
投递腾讯等公司10个岗位
