Posts

Showing posts with the label DP

3. House Robbers

Image
  You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and   it will automatically contact the police if two adjacent houses were broken into on the same night . Given an integer array  nums  representing the amount of money of each house, return  the maximum amount of money you can rob tonight  without alerting the police .   Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2: Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12. Answer: Think of the answer in terms of a decision tree. You can either start at position at index 0 or 1. Since ...

2. Min cost climbing stairs

Image
  You are given an integer array   cost   where   cost[i]   is the cost of   i th   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 . Example 1: Input: cost = [10, 15 ,20] Output: 15 Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15. Example 2: Input: cost = [ 1 ,100, 1 ,1, 1 ,100, 1 , 1 ,100, 1 ] Output: 6 Explanation: You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. The total cost is 6.

1. Climbing Stairs

Image
You are climbing a staircase. It takes   n   steps to reach the top. Each time you can either climb  1  or  2  steps. In how many distinct ways can you climb to the top? Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps  Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Hint: To reach nth step, what could have been your previous steps? (Think about the step sizes) Answer for n=5: Starting at  step 0 , you have  two choices  — move  1 step  (to step 1) or  2 steps  (to step 2). From  step 1 , you can move to  step 2  or  step 3 . From  step 2 , you can move to  step 3  or  step 4 . From  step 3 , you can move to  step 4  or  step 5 . From  step 4 , you can move to  step 5 ...

Dynamic Programming

Image
Understanding Dynamic Programming in Two Stages Dynamic programming (DP) is a way to solve complex problems by breaking them into smaller, overlapping subproblems. It is especially useful when the same subproblems are solved many times in a simple recursive solution. A good way to build a dynamic programming algorithm is to go through two main stages: Stage 1: Develop a Recursive Solution The first step is to describe the problem in terms of smaller versions of itself.  (a) Specification You must clearly define what your recursive function does. For example, for the Fibonacci sequence: Fibonacci series The Fibonacci sequence starts with 0 and 1, and every number after that is the sum of the previous two. (b) Recursive Formula Here is the recursive function written formally:This definition expresses the problem in terms of smaller subproblems: computing `F(n-1)` and `F(n-2)`. The recursive version is easy to understand but slow, because it repeats many calculations. Stage 2: Build t...