LeetCode Q198 House Robber Dynamic Programming

Q198 House Robber

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

 Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

 Example 1:

 Input: [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: [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.

Check solution in Swift at Github:
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q198HouseRobber.playground/Contents.swift

A normal approach to solve problem via Dynamic Programming requires two key steps:

 1. Break down to sub problems

 2. Store results of sub problems in memory array

We will use the results of sub problems for a bigger problem until we get a solution for the whole problem.

 Start thinking about the extremely simple cases - the smallest sub problem

 1. input array has no element, then sum = 0

 2. input array only has one element e.g  [x] _end_ then sum = x,

 we can store this result as memo[length-1] = x

 3. input array has two element [y, x],

 we can go x -> end or y -> end, we should pick Max(x,y)

 memo[length-2] = Max(input[length-1], input[length-2])

 4. input array has three element [z, y, x]

 standing at z, we only need to check which is better? z->x->end? y->end, which means

 since we got the result for

 x->end: memo[length-1]

 y->end: memo[length-2]

 memo[length-3] = Max( (input[length-3] + memo[length-1]), memo[length-2] )

 5. now we've reached

 memo[n] = Max( (input[n] + memo[n+2]), memo[n+1] )

 the remaining thing would be making a for loop to repeat til n == 0

 Time complexity: O(n)

 Space complexity: O(n)

Sample solution

 Now let's try to improve the above solution:

 Hint: everytime we are at memo[n], we only care about memo[n+1] and memo[n+2], we don't need[n+3]....anymore

 So we can just use two variables instead of an array to achieve Space complexity O(1)

Sample solution

Further, we can simplify the second to the solution as below

Hint: everytime we are at index: n, we compare which is better:

    1. rob current and rob the next next

    2. jump current and rob next

And further simplified, 7-line solution!

LeetCode Q70 Climbing Stairs Dynamic Programming VS Recursive

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: 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


Solution:

Sample solution at Github:
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q070ClimbingStairs.playground/Contents.swift

Start thinking about the simpler cases
0 step:  no way to the top, f(0) = 0
1 step: [1] standing at 1, one step to the top, so f(1) =1
2 steps: [2,1]   
    a. standing at 2, one step to 1, another step to the top
    b. standing at 2, two steps directly to the top
    so f(2) = 2
3 steps: [3,2,1]
    standing at 3, 
        a. we can go one step to 2, then there are f(2) ways to the top
        b. we can go two steps to 1, then there are f(1) ways to the top
    f(3) = f(2) + f(1)
Further, for any n-step stairs, there only two options for each step
We see f(n) = f(n-1) + f(n-2)

It's easy to write a recursive solution as above, but recursive function is slower than iteration and requires more memory.

Better solution: Dynamic Programming

The reason why Dynamic Programming is better than recursive is
1. In recursive solution, we start thinking from the biggest f(n), which means solving f(0) and f(1) we need the memory for f(n), f(n-1).... f(2)
1. In Dynamic Programming, we think backward, solve a small problem, save result the small problem and use the result for a bigger problem. In other words, we only need the memory for the current problem we are solving.

Bit Manipulation Problems (5)

Let's look at another medium level problem and solve it with bitwise manipulation

Q318  Maximum Product of Word Lengths



 Use bit operations to mark
 a num:    1        binary:    00000001
 b num:    2        binary:    00000010
 c num:    4        binary:    00000100

 Then we can use | OR operator mark a string contains a, b, c as binary 00000111
 And we can compare if two strings have commom character by checking stringA & stringB != 0
 e.g.
 stringA  "abc" 00000111
 stringB  "ade" 00011001
 stringC  "def" 00111000

 stringA & stringB == 0  -> false
 stringC & stringB == 0  -> true

 We only need 16 bits, so UInt32 is enough for the solution

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q318MaximumProduct.playground/Contents.swift




Other bit manipulation problems in my blog:
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-1.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-2.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-3.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-4.html

More bit manipulation problems at Leetcode:
https://leetcode.com/tag/bit-manipulation/

Bit Manipulation Problems (4)

Let's look at another medium level problem and solve it with bitwise manipulation

Q397 Integer Replacement



Without bit operation, you might think of a solution with time complexity of O(logN),
 since we need a loop for n/2 until n becomes 1

 Let's first look at the mid-results in binary number when n = 8

 num:    8        binary:    00001000
 num:    4        binary:    00000100
 num:    2        binary:    00000010
 num:    1        binary:    00000001

 if the original number takes 4 bits then it will take 4 steps
 so the problem become a shift-operation problem
 we just need >> right-shift to count the bits shifted until the number becomes 0
 and we will be able to write a O(1) solution
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q397IntegerReplacement.playground/Contents.swift



Other bit manipulation problems in my blog:
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-1.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-2.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-3.html

More bit manipulation problems at Leetcode:
https://leetcode.com/tag/bit-manipulation/

Bit Manipulation Problems (3)

Let's look at a medium level problem and solve it with bitwise manipulation

 Q078. Subsets

 Given a set of distinct integers, nums, return all possible subsets (the power set).

 Note: The solution set must not contain duplicate subsets.

 Example:

 Input: nums = [1,2,3]
 Output:
 [
 [3],
 [1],
 [2],
 [1,2,3],
 [1,3],
 [2,3],
 [1,2],
 []
 ]

Solution:

Given a list contains n distinct character
The number of all possible subsets is 2 to the power of n

Take ["A","B","C","D"] as an example and if we use binary number to represent the subset
1 means subset contains that element
 0 means subset doesn't contain that element

We will have
0000 as []
1000 as ["A"]
1001 as ["A", "D"]
1111 as ["A","B","C","D"]
....

Then we will be able to convert the binary number to the subset via bitwise operations '&' and '>>'.
We can start checking the last bit in the binary number and deciding if that element can be put into the subset. Then shift right to check the next last bit.
Check Bitwise Operator Basics


 The range needs to be checked is 0 to 2^n - 1

Example solution
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q078Subsets.playground/Contents.swift



Other bit manipulation problems in my blog:
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-1.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-2.html

More bit manipulation problems at Leetcode:
https://leetcode.com/tag/bit-manipulation/

Bit Manipulation Problems (2)

Bitwise Operation Basics:
https://hadesmercury.blogspot.com/2019/03/bitwise-operator-basics.html
More Bit Manipulation Problems: 

https://leetcode.com/tag/bit-manipulation/

Q342 Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Sample solution:
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q342PowerOfFour.playground/Contents.swift

 num:    4        binary:    00000100
 num:    16        binary:    00010000

 num:    64        binary:    01000000

Similar approach to solve Power of Two. But the difference is the how many bits we care.

Solving Power of Four we care about 3 bits, if the last 3 bits is '100', so instead of & 1 to check the last 3 bits, we use '& 7' (& 111) and we count the number of '100' we have found
if it is '100' we increase the count, return false if the count > 1
if it is '000' we can shift right by 2

if it is other value besides of '100' or '000', then it can not be a power of 4, return false directly




We will be able to find another solution by introducing 0x55555555,
 0x55555555 = 0101 0101 ... 0101
 0xaaaaaaaa   = 1010 1010 ... 1010

For a power of 4: n,  n & 0x55555555 should be n




Other solutions, I am not going to cover so much in this page




The last solution based on the formula, however the solution doesn't work in Swift neither in Java. Try C++.

Bit Manipulation Problems (1)

Bitwise Operation Basics:
https://hadesmercury.blogspot.com/2019/03/bitwise-operator-basics.html


Now we are going to solve problems with the help of  bit operators

Leetcode  Q231  Power of Two
Given an integer, write a function to determine if it is a power of two.
Sample solution:
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q231PowerOfTwo.playground/Contents.swift

A normal approach will be using while loop to divide by 2 and end up with time complexity of O(log n)


If use bit operations, we can achieve time complexity of O(1)
As a power of 2, its binary presentation always contains only-one 1
Coming up with an approach: count the number of 1s
We need >> to shift the bits and '& 1' (& 00000001) to check if the last bit is 1


Another approach:
First, observer binary of n and n - 1

 num:    16        binary:    00010000
 num:    15        binary:    00001111
 num:    32        binary:    00100000
 num:    31        binary:    00011111

If the result of n & (n - 1) should always be 0, if n is a power of 2






We've already solved the problem below, which is similar to the core calculation of isPowerOfTwo1(num: Int)

Q191 Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.




More Bit Manipulation Problems: 
https://leetcode.com/tag/bit-manipulation/

More Solutions - check my other tutorial:
https://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-2.html

LeetCode Q120 Triangle Dynamic Programming

Q120 Triangle




Solution

 level 1:    [2],
 level 2:   [3,4],      [3,4],
 level 3:  [6,5,7],  [7, 6, 10]
 level 4: [4,1,8,3]

 Think from bottom.
 When we at level 3,
 standing at 6, minimum total steps from bottom would be min(6 + 4, 6 + 1) = 7
 standing at 5, minimum total steps from bottom would be min(5 + 1, 5 + 8) = 6
 ...
 Thus, f[level][position] = f[level][position] + min(f[level + 1][position], [level + 1][position + 1])

 And we can just update the total steps from bottom in the array of the current level
 we can modify level 3 : [6,5,7],  -> [7, 6, 10]
 so we don't need any extra space at all.

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q120Triangle.playground/Contents.swift

LeetCode Q064 Minimum Path Sum

Q064 Minimum Path Sum



Similar problem to Unique Path problem
 We can use the same approach
 The difference we store the path sum instead of the number of paths
           [i][j-1]
              |
 [i-1][j] - [i][j]

 minPathToPosition[i][j] = grid[i-1][j-1] + min(minPathToPosition[i - 1][j], minPathToPosition[i][j - 1])

 and for the first row and first column we could not use the default 0 value in the extra row/column
 We can only shift left for first row cells and only shift down for first columns cells
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q064MinimumPathSum.playground/Contents.swift

LeetCode Q053 Maximum Subarray

Q053 Maximum Subarray



Start from the simplest example [-2]
 [-2] the result can only be -2
 We've got f(0) = -2

 Next, 2 numbers
 [-2, 1]
 for 1, the better solution would be ignore -2
 f(1) = max(num(1), num(1) + f(0))

 Thus, f(n): if we choose number[n], what would be the maximum sum of the contiguous subbarray ending at number[m]
 f(n) = max(num[n], num[n] + f(n -1))

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q053MaximumSubarray.playground/Contents.swift

LeetCode Q647 Palindromic Substrings

Q647 Palindromic Substrings




 Palindromic problem basically can be solved with 2D array and dynamica programming
 Since we want to reuse the result for sub problems intead of repeative calculation


Example Solution:
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q647PalindromicSubstrings%20.playground/Contents.swift

LeetCode Q063 Unique Paths II

Q063 Unique Paths II



The only difference compared to Q060

 for those positions obstacle[i][j] == 1 has an obstacle, there is no path to go there, so we should put pathsToPosition[i][j] == 0
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q063UniquePathsII.playground/Contents.swift

LeetCode Q045Jump Game II (hard)

Q045Jump Game II (hard)



    We have to reach the last index with minimum jumps, so we should jump at the step with the largest number if possible.


    Let's take [2,3,1,5,4] as example
             [2,3,1,1,4]
 index    0 1 2 3 4

 var countJump = 0
 var maxReach = 0
 var prevReach = 0

 1. we have to jump at the nums[0]: 2, the maximum index we can reach is 2, maxReach = 2
 2. check index = 1, this is the place we have to jump
    if index > prevReach, we increase：countJump = 1,
    every time we jump update the prevReach = maxReach = 2
    maxReach = 1 + 3 = 4
 3. check index = 2, maxReach = max(maxReach, 2+1) = 4
 4. check index = 3, greater than prevReach, means this is the place we only can reach by jump, so just like step 2
    countJump = 2, prevReach = 4
    maxReach = max(4, 4) = 4
 5. check index = 4, <= maxReach
    maxReach = max(4, 4+4) = 8
 6. loop ends

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/Greedy/Q045JumpGameII.playground/Contents.swift

LeetCode Q452 Minimum Number of Arrows to Burst Balloons

Q452 Minimum Number of Arrows to Burst Balloons




 1. Sort by start point then end point, we might get the sorted ballons as below
        ---------
          ------
             ---------
                    ------
                    ---------
 2. In order to sort as more balloons as possible, try to shot at the end point
 starting at the endpoint of ballon 1, record it as the arrow
 check the next ballon, if we find the start point is smaller than arrow which means we can try to adjust the arrow to shot it by this arrow, by min(endpoint, arrow)
 (In the above example, the first shot would be at the end point of 2th balloon, at shot 1,2,3 together, since the start point of 4th is greater than the arrow. So once we shot 1-3, we have to do another shot for the 4th, update the count.)

 And we have to repeat the above steps from 4th balloon, assume the next shot is at endpoint of 4th

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/Greedy/Q452MinArrows.playground/Contents.swift

LeetCode Q330 Patching Array (Hard)

Q330. Patching Array (Hard)



 We have to check every number from 1 ~ n      miss: Int
 We should keep an index pointer to record if we have checked all the number within the array  index:Int

 We have to loop until miss == n
 Everytime we should compare if all the elements have been used

 If not all used
 Then compare if miss >= nums[index]
 YES: we've covered [1, miss - 1], since nums[index] is also smaller that miss, the whole range has been covered is [1, miss - 1 + nums[index]], we can update miss
 NO:  have to insert miss, [1, miss * 2 - 1] will be covered by the sum of the elements in array, so update miss = miss * 2


 If all used: insert miss then, [1, miss * 2 - 1] will be covered by the sum of the elements in array, so update miss = miss * 2

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/Greedy/Q330.PatchingArray.playground/Contents.swift

LeetCode Q060 Unique Paths

Q060 Unique Paths



Thinking from bottom to top. 
For the finish position which is pathsToPosition[m][n], there are two ways to go there
from left position [m - 1][n] or top position [m][n - 1]. Same for any other positions.

So we can start from the top left position which there is only 1 way to reach
Then write nested for loop to check for all the other positions
Until reaching [m][n] which is the final result

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q060UniquePaths.playground/Contents.swift

LeetCode 877. Stone Game

Q877 Stone Game




 Interestly, the first player can always have the control to collect all the numer at the even index or odd index. If the sum of nums at even index is greater then sum of odd index, then just select sum of even index.

 Is that true the first player always has the control?
 [4, 3, 1, 7, 2, 1]
 Assume I am the first player and I found 4 + 1 + 2 < 3 + 7 + 1
 The question now becomes can I get  3, 7, 1
 YES, I can choose the last 1 first, the next player could choose 4 or 2 from [4, 3, 1, 7, 2]
 If he chooses 4 then I choose 3
 If he chooses 2 then i choose 7

 So the first player always wins.

LeetCode Q303 Range Sum Query - Immutable

Q303 Range Sum Query - Immutable




  Since the sumRange will be called many times
  We should think a way that to reuse the sums

  This apprach only travers the array once and store sum of 0th to n-th
  Input  [-2, 0, 3, -5, 2, -1]
  Record [-2, -2, 1, -4, -2, -3]

  sumRange(i,j) = sum[j] - sum[i - 1]

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q303RangeSumQuery.playground/Contents.swift

LeetCode Q338 Counting Bits

Q338 Counting Bits



 num:    1        binary:    00000001
 num:    2        binary:    00000010
 num:    3        binary:    00000011
 num:    4        binary:    00000100
 num:    5        binary:    00000101
 num:    6        binary:    00000110
 num:    7        binary:    00000111
 num:    8        binary:    00001000
 num:    9        binary:    00001001
 num:    10        binary:    00001010
 num:    11        binary:    00001011
 num:    12        binary:    00001100
 num:    13        binary:    00001101
 num:    14        binary:    00001110
 num:    15        binary:    00001111

 Define f(n) number of 1s in binary presentation for n
 for number  2^i<= n < 2^(i-1)
 f(n) = 1 + f(n % 2^i)

Example Solution

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q338CountingBits.playground/Contents.swift

LeetCode Q1025 Diviser Game

 Q1025 Diviser Game


0 < x < N, replace x with N - x, Alice always starts first

 N = 0 or N = 1, no one is able to play this game
 N = 2, Alice: 1, make the problem as f(N = 1) = false for Bob, Alice wins
 N = 3, Alice can only choose 1, make the problem as f(N = 2) == true, Alice lose
 N = 4, Alice can choose 1 or 2, to make the problem as f(N = 3) or f(N = 2), apparently Alice should choose 1 to win
 N = 5, Alice can only choose 1, f(N = 4) bob win
 .......
 seems there is a pattern, for even number Alice can always win but not odd (Actually, that is true)

 N = 12, 1? Yes, Alice wins
         2?  f(N = 10) for bob to win
         3?  f(N = 9)  for bob, Alice will win
 N = 15  1? Yes
         3? f(12) bob will win
         5? f(10) bob will win
 .....

 Findings;
 1. If Alice got a even number, she can alwasy pass back a odd number to bob
 2. If Alice got a odd number, divider can only be odd number, odd - odd = even

 For any N, finally we will always go back to f(2) f(3)
 Starting from a odd number, Alice can only pass f(even) to Bob
 Starting from a even number, Alice can always get f(2) to herself

 Win or not just depends on the number is even or odd.

 Pretty strait forward solution is just : return N % 2 == 0

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/1025DivisorGame.playground/Contents.swift

Dynamic Programming