Dynamic Programming

X. DP
- Space compression
- Interval DP - O(N^3)
- Simplify DP relation
Usually we can also use dfs + cache

When to use dp
- When to get the number of X

Save space - O(n) instead of O(mn), O(1) instead ofO(n)
O(1): Use and modify original input

Two string => use dp[s.length][p.length]

X. How to fill the dp array
X. Fill First Row and Column, then row by row
LeetCode 115 -  Distinct Subsequences
X. diagonal by diagonal, len++
--->
     ^
      |
LeetCode 516 - Longest Palindromic Subsequence
https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution
dp[i][j]: the longest palindromic subsequence's length of substring(i, j)
dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
Initializationdp[i][i] = 1
2: bottom row to top row - along diagonal
https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution

坐标型
单序列型
双序列型
区间型

Interval DP - O(N^3)
LintCode 476 - Stone Game
At each step of the game,the player can merge two adjacent piles to a new pile.
The score is the number of stones in the new pile.
You are to determine the minimum of the total score.
dp[i][j]=dp[i][k]+dp[k+1][j]+sum[i][j]
- presum

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
- Simplify DP relation
dp[i][j] //represent the number of permutations of (1...n) with k inverse pairs.
dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]
dp[n][k+1] = dp[n][k]+dp[n-1][k+1]-dp[n-1][k+1-n]

Lintcode 43 - Maximum Subarray III
find k non-overlapping subarrays which have the largest sum.
dp[i][j] - the maximum total sum of choosing i subarrays from the first j number
dp[i][j] = max(dp[i - 1][t] + maxSubarraySum(nums[t+1...j]))

find two non-overlapping subarrays which have the largest sum



X. Multi-relation DP
Count binary strings with k times appearing adjacent two set bits
Let there be an array dp[i][j][2] where dp[i][j][0]
denotes number of binary strings with length i having
j number of two adjacent 1's and ending with 0.
Similarly dp[i][j][1] denotes the same binary strings
with length i and j adjacent 1's but ending with 1.
    dp[1][0][0] = 1 and dp[1][0][1] = 1
    For all other i and j,
        dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]
        dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1]

X. Tough to find DP
From its DFS(brute force), figure out what's the state, what's changing

X. Reminder
Number of subsequences in a string divisible by n
    // division by n can leave only n remainder
    // [0..n-1]. dp[i][j] indicates number of
    // subsequences in string [0..i] which leaves
    // remainder j after division by n.
    int dp[len][n];


X. Palindrome
boolean[][] isPalindrome

Maximum subsequence sum such that no three are consecutive
- sum[i] is depended on, all cases

LeetCode 416 - Partition Equal Subset Sum
boolean[] dp = new boolean[sum + 1];
boolean[][] dp = new boolean[n+1][sum+1];
(a) including the last element
(b) excluding the last element
3 Partition Problem
K Partition Problem


Longest Zig-Zag Subsequence - GeeksforGeeks
Z[i][0] = Length of the longest Zig-Zag subsequence 
          ending at index i and last element is greater
          than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence 
          ending at index i and last element is smaller
          than its previous element
Recursive Formulation:
   Z[i][0] = max (Z[i][0], Z[j][1] + 1); 
             for all j < i and A[j] < A[i] 
   Z[i][1] = max (Z[i][1], Z[j][0] + 1); 
             for all j < i and A[j] > A[i]

LeetCode 241 - Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

DFS+Cache: https://discuss.leetcode.com/topic/19908/java-recursive-solution-with-memorization

Leetcode 44 - Wildcard Matching
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).
    public boolean isMatch(String s, String p) {
        if (p == null || p.length() == 0) {
            return s == null || s.length() == 0;
        }
         
        int rows = s.length();
        int cols = p.length();
         
        boolean[][] dp = new boolean[rows + 1][cols + 1];
         
        dp[0][0] = true;
        for (int j = 1; j <= cols; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            } else break;//
        }
         
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (p.charAt(j - 1) != '*') {
                    if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
         
        return dp[s.length()][p.length()];
    }
X. O(n) space
http://bangbingsyb.blogspot.com/2014/11/leetcode-wildcard-matching.html
https://discuss.leetcode.com/topic/10794/my-java-dp-solution
http://happycoding2010.blogspot.com/2015/09/leetcode-43-wildcard-matching.html
   public boolean isMatch(String s, String p) {  
     int m=s.length();  
     int n=p.length();  
     boolean[] dp=new boolean[n+1];  
     for (int i=0; i<=m; i++) {  
       boolean pre=false;  //\\
       for (int j=0; j<=n; j++) {  
         boolean temp=dp[j];  
         if (i==0) {  
           if (j==0) dp[j]=true;  
           else if (p.charAt(j-1)=='*') dp[j]=dp[j-1];  
           else dp[j]=false;  
         }  
         else if (j==0) dp[j]=false;  
         else if (p.charAt(j-1)=='?') dp[j]=pre;  
         else if (p.charAt(j-1)=='*') dp[j]=dp[j] || dp[j-1];  
         else if (s.charAt(i-1)==p.charAt(j-1)) dp[j]=pre;  
         else dp[j]=false;  
         pre=temp;  
       }  
     }  
     return dp[n];  
   }  

X. Two pointers TODO
https://yujia.io/blog/2015/11/15/LeetCode-44-Wildcard-Matching/
        bool isMatch(string s, string p) {
            auto n = s.size(), m = p.size();
            int j = 0;
            for(int i = 0, lastp = -1, lasts = -1; i != n;){
                if ((s[i] == p[j]) || (p[j] == '?')){
                    i++; j++;
                }else if (p[j] == '*'){
                    j++;
                    lastp = j;
                    lasts = i;
                }else if (lastp != -1){
                    j = lastp;
                    i = ++lasts;
                }else
                    return false;
            }
            for (; (j < m) && (p[j] == '*'); j++);
            return (j == m);
        }
};


LeetCode 10 - Regular Expression Matching
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
https://discuss.leetcode.com/topic/40371/easy-dp-java-solution-with-detailed-explanation
https://segmentfault.com/a/1190000003904286
1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
               1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
               2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                              dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty
public boolean isMatch(String s, String p) {

    if (s == null || p == null) {
        return false;
    }
    boolean[][] dp = new boolean[s.length()+1][p.length()+1];
    dp[0][0] = true;
    for (int i = 0; i < p.length(); i++) {
        if (p.charAt(i) == '*' && dp[0][i-1]) {
            dp[0][i+1] = true;
        }
    }
    for (int i = 0 ; i < s.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == '.') {
                dp[i+1][j+1] = dp[i][j];
            }
            if (p.charAt(j) == s.charAt(i)) {
                dp[i+1][j+1] = dp[i][j];
            }
            if (p.charAt(j) == '*') {
                if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                    dp[i+1][j+1] = dp[i+1][j-1];
                } else {
                    dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}
O(n) space
https://discuss.leetcode.com/topic/31974/java-4ms-dp-solution-with-o-n-2-time-and-o-n-space-beats-95
https://discuss.leetcode.com/topic/6388/sharing-my-44ms-dp-code-o-mn-time-and-o-n-space

LeetCode 73 - Unique Paths II
http://buttercola.blogspot.com/2014/09/leetcode-unique-paths-ii.html
https://discuss.leetcode.com/topic/39698/share-my-2ms-java-solution-with-o-1-spqce
public int numDecodings(String s) {
    if(s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
 int curWays = 1;
 int preWays = 1;
 int length = s.length();
 for(int i = 1; i < length; i++){
  int newCurWays = curWays;
  if(s.charAt(i) == '0'){
   if(s.charAt(i - 1) != '1' && s.charAt(i - 1) != '2') return 0;
   else newCurWays = preWays; 
  }else if(s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) < '7')){
   newCurWays += preWays;
  }
  preWays = curWays;
  curWays = newCurWays;
 }
 return curWays;
}

LeetCode Edit Distance
https://discuss.leetcode.com/topic/20922/java-dp-solution-o-nm
https://discuss.leetcode.com/topic/6965/standard-dp-solution
https://discuss.leetcode.com/topic/27929/concise-java-dp-solution-with-comments
public int minDistance(String word1, String word2) {
 // dp[i][j] : minimum steps to convert i long word1 and j long word2
 int dp[][] = new int[word1.length() + 1][word2.length() + 1];

 for (int i = 0; i <= word1.length(); i++) dp[i][0] = i;     
 for (int j = 0; j <= word2.length(); j++) dp[0][j] = j; 
  
 for (int i = 1;i <= word1.length(); i++) {
  for (int j = 1; j<= word2.length(); j++) {
   if (word1.charAt(i-1) == word2.charAt(j-1))// <-- 1="" :="" because="" code="" delete="" dp="" else="" i-1="" i="" j-1="" j="" math.min="" replace="" return="" with="" word1.length="" word1="" word2.length="" word2="" word="">
Rolling Array
http://gongxuns.blogspot.com/2012/12/edit-distance-given-two-words-word1.html
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        if(m==0) return n;
        if(n==0) return m;
        
        int[] distances = new int[n+1],old = new int[n+1]; 
        for(int i=0;i<=n;i++)
            old[i]=i;

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1))
                    distances[j] = j>1?old[j-1]:(i-1);
                else
                    distances[j] = 1+Math.min(j>1?old[j-1]:(i-1),Math.min(old[j],j>1?distances[j-1]:i));
            }
            for(int j=1;j<=n;j++)
                old[j]=distances[j];
        }
        return old[n];
    }

https://discuss.leetcode.com/topic/11723/my-clean-java-solution-with-o-n-space-in-17-lines
    public int minDistance(String word1, String word2) {
        int[] d = new int[word2.length() + 1];
        for (int i = 0; i <= word2.length(); ++i) d[i] = i;
        for (int i = 1; i <= word1.length(); ++i) {
            int prev = d[0];
            d[0] = i;
            for (int j = 1; j <= word2.length(); ++j) {
                int tmp = d[j];
                d[j] = Math.min(d[j - 1], d[j]) + 1;
                d[j] = Math.min(d[j], prev + (word1.charAt(i -1) == word2.charAt(j - 1) ? 0: 1));
                prev = tmp;
            }
        }
        return d[word2.length()];
    }

LeetCode 87 - Scramble String
http://www.lifeincode.net/programming/leetcode-scramble-string-java/
    public boolean isScramble(String s1, String s2) {
        //Check lengths.
        if (s1.length() != s2.length())
            return false;
        if (s1.equals(s2))
            return true;
            
        int L = s1.length();
        boolean[][][] scramble = new boolean[L][L][L];
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < L; j++)
                if (s1.charAt(i) == s2.charAt(j))
                    scramble[0][i][j] = true;
        }
        
        for (int k = 2; k <= L; k++) {
            for (int i = L - k; i >= 0; i--) {
                for (int j = L - k; j >= 0; j--) {
                    boolean canScramble = false;
                    for (int m = 1; m < k; m++) {
                        canScramble = (scramble[m - 1][i][j] && scramble[k - m - 1][i + m][j + m]) || (scramble[m - 1][i][j + k -m] && scramble[k - m - 1][i + m][j]);
                        if (canScramble)
                            break;
                    }
                    scramble[k - 1][i][j] = canScramble;
                }
            }
        }
        
        return scramble[L - 1][0][0];
    }
DFS + Prune
https://discuss.leetcode.com/topic/19158/accepted-java-solution
https://discuss.leetcode.com/topic/23691/java-fast-dp-iteration-solution-and-recursion-solution

Lintcode: K Sum I
Given n distinct positive integers, integer k (k <= n) and a number target. Find k numbers where sum is target. Calculate how many solutions there are?
http://www.jiuzhang.com/solutions/k-sum/
    public int  kSum(int A[], int k, int target) {
        int n = A.length;
        int[][][] f = new int[n + 1][k + 1][target + 1];
        for (int i = 0; i < n + 1; i++) {
            f[i][0][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    f[i][j][t] = 0;
                    if (t >= A[i - 1]) {
                        f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                    }
                    f[i][j][t] += f[i - 1][j][t];
                } // for t
            } // for j
        } // for i
        return f[n][k][target];
    }
http://www.cnblogs.com/yuzhangcmu/p/4279676.html
https://github.com/yuzhangcmu/LeetCode/blob/master/lintcode/dp/KSum.java
public int  kSum(int A[], int k, int target) {
    // write your code here
    if (target < 0) {
        return 0;
    }

    int len = A.length;

    // D[i][j]: k = i, target j, the solution.
    int[][] D = new int[k + 1][target + 1];

    // only one solution for the empty set.
    D[0][0] = 1;
    for (int i = 1; i <= len; i++) {
   
            for (int j = 1; j <= k; j++) {
                for (int t = target; t > 0; t--) {
                if (t - A[i - 1] >= 0) {
                    D[j][t] += D[j - 1][t - A[i - 1]];
                }
            }
        }
    }

    return D[k][target];
}

LeetCode 97 - Interleaving String
https://discuss.leetcode.com/topic/7728/dp-solution-in-java
https://discuss.leetcode.com/topic/5087/my-solution-in-java-using-dp-time-o-n-m-and-space-o-m
X. BFS
https://discuss.leetcode.com/topic/30127/summary-of-solutions-bfs-dfs-dp
https://discuss.leetcode.com/topic/6562/8ms-c-solution-using-bfs-with-explanation/11


Post a Comment

Labels

Java (159) Lucene-Solr (110) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Troubleshooting (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Http Client (8) Maven (8) Problem Solving (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) System Design (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts