Minimum cost to climb stairs
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
// Bottom up tabulation - O(n) 1ms
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n];
for (int i=0; i<n; i++) {
if (i<2) dp[i] = cost[i];
else dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
}
return Math.min(dp[n-1], dp[n-2]);
}Related Problems
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.