Leetcode -- 322. Coin Change(DP)

322. Coin Change(DP)
Medium
https://leetcode.com/problems/coin-change/#/description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

思路：-  use dp bottom up, memoization method
          - we know each solution is formed by at least 1 existing coin, so we check if dp[i-coin] exists.
          - keep filling dp[i] with the min
Complexity: Time O(m*n) -  m is amount, n is len of coins,  Space O(m) - dp array

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];//0,1,2,..,amount
        for(int i = 1; i <= amount; i++){
            int count = -1;
            //key is min count, all solutions must be generated from existing coin
            for(int coin : coins) {
             if(i >= coin && dp[i-coin]!=-1) {//skip non-existing solution
              int cur = dp[i-coin]+1;
              if(count < 0)
                  count  = cur;
              else if(cur < count)
                  count = cur;
             }
         }
         dp[i] = count;
        }
        return dp[amount];
    }

Leetcode/各大家 -- 10. Regular Expression Matching(DP)

10. Regular Expression Matching(DP)
hard
https://leetcode.com/problems/regular-expression-matching/

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

 Google Uber Airbnb Facebook Twitter

思路： 见图， 1. 事先要把0presense的情况标好
                        2. 填数组，watch几个关键情况

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        //handle 1st row dealing a*b* - 0 presence, mark such * true
        for(int j = 1; j < dp[0].length; j++){
            if(p.charAt(j-1) == '*')
                dp[0][j] = dp[0][j-2];    
        }
        for(int i = 1; i < dp.length; i++){
            for(int j = 1; j < dp[0].length; j++){
                char sc = s.charAt(i-1);
                char pc = p.charAt(j-1);
                if(pc == sc || pc == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(pc == '*'){
                    if(dp[i][j-2]){
                        dp[i][j] = true;//0 presence of pre letter
                    }else if(p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'){
                        dp[i][j] = dp[i-1][j];
                    }
                }
                //both different letter, fill false
            }
        }
        return dp[s.length()][p.length()];
    }
}

Leetcode/各大家 -- 377. Combination Sum IV(DP)

377. Combination Sum IV (DP)
medium

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Google Snapchat Facebook

思路1：DP - Fill each dp[i] from 0 to target indicating the possibilites to sum to i;
          To fill each dp[i], we check through nums and pick any of element possible, at which it has target dp[target-nums[i]] possibility

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++){//fill dp[i], indicates ways to sum to i
            for(int j = 0; j < nums.length; j++){//calculate each dp[i]
                if(i - nums[j] >= 0){
                    dp[i] += dp[i - nums[j]];  
                } 
            }
        }
        return dp[target];
    }
}

eg:
nums[1,2,3] target = 4

dp[0, 1, 2, 3, 4] return dp[4]
   1, 1, 2, 4, 7
dp[4] = dp[4-1] + dp[4-2] + dp[4-3] = dp[3] + comb[2] + comb[1].
7 is from  1(dp of nums[0] = dp[1])+2(dp of nums[1])+4(dp of nums[2])
To get 4, when at dp[4], we can choose any num[i] in nums and so it will have target-nums[i] possibility

思路2： top-down recursion with hashmap
https://discuss.leetcode.com/topic/52255/java-recursion-solution-using-hashmap-as-memory

Leetcode -- 338. Counting Bits(DP)

338. Counting Bits(DP)
medium
https://leetcode.com/problems/counting-bits/

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

思路： use dp, find the relation that dp[i] = dp[i-offset] + 1, offset: 0,1,2,4,8..
          eg dp[4] = d[4-4]+1 = 1, dp[6] = dp[6-4] + 1 = dp[2] + 1 = 2
Complexity:  time-O(N), SpaceO(N)

public class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        int offset = 1;
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            if(offset * 2 == i) offset = i;
            dp[i] = dp[i - offset] + 1;
        }
        return dp;
    }
}

Leetcode/F家微软 -- 91. Decode Ways(DP)

91. Decode Ways(DP)
medium
https://leetcode.com/problems/decode-ways/ 

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

 Microsoft Uber Facebook

思路： use dp to add through string. Prefill dp[0] 1. For  current char,
1 - If cur.val != 0, dp[i+1](cur) = dp[i](pre) - inherit last char (we treat cur as one letter)
2 - If cur.val + pre.val * 10 in [10,26], dp[i+1] += dp[i-1] - add 2nd last char(we treat cur&last as one letter)
Complexity: Time O(n) Space O(n)

//invalid case: 001, 1001 ..., return 0
    public int numDecodings(String s) {
        if(s.length() == 0||s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];//need prefill 2 val in dp
        dp[0] = 1;//default val
        dp[1] = 1;//filled by 1st char in s
        for(int i = 1; i < s.length(); i++){
            int pre = s.charAt(i-1) - '0';
            int cur = s.charAt(i) - '0';
            if(cur != 0){//no char for single 0
                dp[i+1] = dp[i];
            }
            int sum = pre*10 + cur;
            if(sum >= 10 && sum <=26){//eg:01 not valid, only bt [10,26]
                dp[i+1] += dp[i-1];
            }
        }
        return dp[dp.length - 1];
    }

/*125  127
  ABE   ABG 
   LE    LG
   AY   
----------
   3     2 
*/

Leetcpde -- 263.264 Ugly Number(Recur) + II(DP)

263.264 Ugly Number + II
easy/medium

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

263 I. only need to decide if ugly number, return true/false.
思路： keep mod and divide 2,3,5 till base case.

public class Solution {
    public boolean isUgly(int num) {
        if(num <= 0) return false;
        if(num == 1) return true;
        if(num%2 == 0){
            return isUgly(num/2);
        }
        if(num%3 == 0){
            return isUgly(num/3);
        }
        if(num%5 == 0){
            return isUgly(num/5);
        }
        return false;
    }
}

264 II.
思路1： use dp[n] to track next ugly number

public class Solution {
    public int nthUglyNumber(int n) {
        int i1 = 0, i2 = 0, i3 = 0;
        int num1 = 2,num2 = 3,num3 = 5;//ugly number: 1,2,3,5,
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            dp[i] = Math.min(num1, Math.min(num2, num3));
            if(dp[i] == num1){
                i1++;
                num1 = 2*dp[i1];
            }
            if(dp[i] == num2){
                i2++;
                num2 = 3*dp[i2];
            }
            if(dp[i] == num3){
                i3++;
                num3 = 5*dp[i3];
            }
        }
        return dp[n-1];
    }
}

思路2： use heap to return the min, keep adding min*2, min*3, min*5 and minus n, till n == 0
slow

ublic class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        long res = 0;
        heap.add((long)1);
        while(!heap.isEmpty() && n > 0){
            while(res == heap.peek()){
                heap.poll();
                continue;
            }
            res = heap.poll();
            heap.add(res * 2);
            heap.add(res * 3);
            heap.add(res * 5);
            n--;
        }
        return (int)res;
    }
}

Leetcode/各大家 -- 221. Maximal Square(DP)

221. Maximal Square(DP)
Medium
https://leetcode.com/problems/maximal-square/

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

 Apple Airbnb Facebook

思路： initialize dp[m+1][n+1], dp[i][j] indicating the max length of square at current position
           when a[i-1][j-1] = 1遇到1元素，dp[i][j]是左上，正上，左中的min +1

public class Solution {
    public int maximalSquare(char[][] a) {
      if(a == null || a.length == 0 || a[0].length == 0)return 0;
      int m = a.length, n = a[0].length;
      int[][] dp = new int[m+1][n+1];//is the max len of maximal square at current pos
      int max = 0;
      //dp: when a[i-1][j-1] = 1, dp[i][j] = 1 + Min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])
      for(int i = 1; i < m+1; i++){
          for(int j =1 ;j < n+1; j++){
              if(a[i-1][j-1] == '1'){
                  dp[i][j] = 1 + Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]));
                  max = Math.max(max,dp[i][j]);
              }
          }
      }
      return max*max;
    }
}

Leetcode/微软-- 300. Longest Increasing Subsequence(DP)

300. Longest Increasing Subsequence(DP)

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

思路：double loop, j is element before i, dp[i] is current element seq max length eg[3,4,-1,0,6,2,3]

arr[j] < arr[i]: dp[i] is Max(dp[j]+1,dp[i])
                  //not update i if i already bigger(results from previous: 3,4,6; so not update when get to -1)
else not increaing: j++
once j=i: i++,j=0

Complexity: O(n^2)

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length<=1)return nums.length;
        int[]dp= new int[nums.length];
        int max = 1;
        for(int i=0;i<dp.length;i++)
            dp[i]=1;
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){//increasing
                    dp[i] = Math.max(dp[j]+1,dp[i]);
      max = Math.max(dp[i],max);
                }
            }
        }
        return max;
    }
}