使用最小花费爬楼梯
时间: 2023-07-11 10:19:29 浏览: 54
好的,这是一道比较经典的动态规划问题,以下是详细解答:
题目描述:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你可以使用最少的花费爬完楼梯,其中每个台阶对应的花费是一个非负整数。你可以从第 0 阶或者第 1 阶开始爬台阶。
示例:
输入: cost = [0, 1, 2, 3, 4]
输出: 2
解释: 爬到楼顶共需要花费 2 或 3 或 4 元。
解题思路:
这道题可以用动态规划来解决,具体思路如下:
1. 定义状态:dp[i] 表示到达第 i 个台阶所需要的最小花费。
2. 初始化:dp[0] = cost[0],dp[1] = cost[1]。
3. 状态转移:对于第 i 个台阶,可以从第 i-1 个台阶爬上来,也可以从第 i-2 个台阶爬上来。所以状态转移方程为:dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
4. 最终结果:最后返回 dp[n-1] 和 dp[n-2] 中的较小值即可。
代码实现:
```java
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < n; i++) {
dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
}
return Math.min(dp[n-1], dp[n-2]);
}
```