Min Cost Climbing Stairs, DP Solution

-
One more problem that cab be solved using DP: https://leetcode.com/problems/min-cost-climbing-stairs/description/

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Note:
  1. cost will have a length in the range [2, 1000].
  2. Every cost[i] will be an integer in the range [0, 999].
Same hints as seen before: looking for min/max, a "cost" function used as the weight, combinatorial is intractable.
Solution is by construction, rather than by induction. Have a DP array which will hold the best solution up to staircase "i". Then build it from 0,1,...,N. At the end, the solution will be either the last element in DP, or the last minus one, whichever is the smallest. Code is below, cheers, Boris.


public class Solution
{
 public int MinCostClimbingStairs(int[] cost)
 {
  if (cost == null) return 0;

  int[] dp = new int[cost.Length];

  //Base
  dp[0] = cost[0];
  dp[1] = cost[1];

  //Construction
  for (int i = 2; i < cost.Length; i++)
   dp[i] = cost[i] + Math.Min(dp[i - 1], dp[i - 2]);

  return Math.Min(dp[dp.Length - 1], dp[dp.Length - 2]);
 }
}

Comments

  1. TarasDecember 22, 2018 at 9:11 PM

    So many memories today - I was asked this problem on my very first Google screen interview. My solution at the time was very similar and used unnecessary linear amount of extra memory, even though all we need is 2 previous costs. The solution with O(1) memory usage is:

    class Solution {
    public:
    int minCostClimbingStairs(const vector& cost) {
    int n_2 = cost.front();
    int n_1 = cost[1];
    for (int i = 2; i < cost.size(); ++i) {
    int new_cost = cost[i] + min(n_2, n_1);
    n_2 = n_1;
    n_1 = new_cost;
    }
    return min(n_2, n_1);
    }
    };

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more