动态规划攻略之：用最小花费爬楼梯

动态规划攻略之：用最小花费爬楼梯

题目

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例1：

输入：cost = [10, 15, 20]输出：15解释：最低花费是从 cost[1]

示例2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]输出：6解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3]

解题思路

根据题目要求，我们可以利用动态规划的思路来解题。

首先，到达第 i 级台阶的阶梯顶部的最小花费，有俩个选择：

先付出最小总花 minCost[i-1] 到达第i级台阶（第i-1级台阶的阶梯顶部），踏上第i级台阶需要再花费 cost[i]，再迈一步到达第i级台阶的阶梯顶部，最小总花费为minCost[i-1] + cost[i])；先付出最小总花费 minCost[i-2] 到达第i-1级台阶（第i-2级台阶的阶梯顶部），踏上第i-1级台阶需要再花费 cost[i-1]，再迈两步跨过第i级台阶直接到达第i级台阶的阶梯顶部，最小总花费为minCost[i-2] + cost[i-1])；

则minCost[i]是上面这两个最小总花费中的最小值。

因此状态转移方程如下：

minCost[i] = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])。

代码实现

class Solution { public int minCostClimbingStairs(int[] cost) { int size = cost.length; int[] minCost = new int[size]; minCost[0] = 0; minCost[1] = Math.min(cost[0], cost[1]); for (int i = 2; i < size; i++) { minCost[i] = Math.min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]); } return minCost[size - 1]; }}

最后

时间复杂度为：O(N)

空间复杂度为：O(N)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。