Runtime: 7 ms, faster than 7.42% of Java online submissions for Min Cost Climbing Stairs. Memory Usage: 45.9 MB, less than 5.68% of Java online submissions for Min Cost Climbing Stairs.
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public int minCostClimbingStairs(int[] cost) {
return Math.min(minCostClimbingStairs(cost, 0),
minCostClimbingStairs(cost, 1));
}
public int minCostClimbingStairs(int[] cost, int stair) {
if(map.containsKey(stair))
return map.get(stair);
if(stair >= cost.length)
return 0;
int pay = cost[stair];
pay = pay + Math.min(minCostClimbingStairs(cost, stair + 1),
minCostClimbingStairs(cost, stair + 2));
map.put(stair, pay);
return pay;
}
}