05 August 2008
一维数组每个元素是每一步的cost，每次可以爬一步或两步，找到爬上顶部最省costs的路径，返回最小的cost
Recurrence Relation:
mincost(i) = cost[i]+min(mincost(i-1), mincost(i-2))
Base cases:
mincost(0) = cost[0] mincost(1) = cost[1]
朴素递归
1
2
3
4
5
6
7
8
9
10
// Recursive Top Down - O(2^n) Time Limit Exceeded
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
return Math.min(minCost(cost, n-1), minCost(cost, n-2));
}
private int minCost(int[] cost, int n) {
if (n < 0) return 0;
if (n==0 || n==1) return cost[n];
return cost[n] + Math.min(minCost(cost, n-1), minCost(cost, n-2));
}
三种优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Top Down Memoization - O(n) 1ms
int[] dp;
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
dp = new int[n];
return Math.min(minCost(cost, n-1), minCost(cost, n-2));
}
private int minCost(int[] cost, int n) {
if (n < 0) return 0;
if (n==0 || n==1) return cost[n];
if (dp[n] != 0) return dp[n];
dp[n] = cost[n] + Math.min(minCost(cost, n-1), minCost(cost, n-2));
return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Bottom up tabulation - O(n) 1ms
class Solution {
// dp[n] = min(dp[n - 1], dp[n - 2]) + cost[i]
public int minCostClimbingStairs(int[] cost) {
if (cost == null || cost.length == 0) {
return 0;
}
int len = cost.length;
int[] dp = new int[len];
for (int i = 0; i < len; i++) { //跳过dp[0]，也可以不跳过
if (i < 2) { // 初始化
dp[i] = cost[i];
} else {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
}
return Math.min(dp[len - 1], dp[len - 2]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// Bottom up computation - O(n) time, O(1) space
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int first = cost[0];
int second = cost[1];
if (n<=2) return Math.min(first, second);
for (int i=2; i<n; i++) {
int curr = cost[i] + Math.min(first, second);
first = second;
second = curr;
}
return Math.min(first, second);
}