X. DP
- Space compression
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
otherwise,
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
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]))
X. Multi-relation DP
Count binary strings with k times appearing adjacent two set bits
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
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
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
- Space compression
- Interval DP - O(N^3)
- Simplify DP relation
Usually we can also use dfs + cacheWhen 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])Initialization: dp[i][i] = 12: 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]))
- Related Lintcode 42 - Maximum Subarray II
find two non-overlapping subarrays which have the largest sumX. 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()]; }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-explanationhttps://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 emptypublic 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()];
}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="">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 + Prunehttps://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
