2-6-2018 subsequence & DP
Longest Increasing Subsequence
DP 经典题
naive BF method: : If we use '0' or '1' to represent whether we choose this num or not, we can enumerate all the combinations so that we can check if this is a sorted subsequence. The time complexity is at least O(2^n).
particularly, we can use DFS recursion to find all increasing subsequences and then returning the maximum length of longest increasing subsequence.. for every character, we should consider two cases:
The current element is larger than the previous element included in the LIS, so we can include the current element in the LIS.
The current element is smaller than the previous element included in the LIS. In this case, we can't include the current element in the LIS.
in the end, we just return the larger one. refer to recursion DFS Time complexity is O(2^n), Space: O(n^2)
Think further, we can use memorization to optimize the above algorithm. Because we notice that recursive calls will be made again and again with the same parameters.
memo[i][j] represents the length of the LIS possible using nums[i] as the previous element considered
to be included/not included in the LIS, with nums[j] as the current element considered to be included/not
included in the LIS.
refer to DP with memorization, but the Space complexity is still O(n^2)
Think further, how to do it using DP from bottom to up?
Def: 定义LIS(array): Length of the LIS that ends with array[n-1]
how to solve LIS(array) ? we need to find all the subarray that the last element(e.g. 7) is less than the current last number(e.g. 18). Because in this case, we can form a LIS. So, we can recursive get the length of those LIS, and get the largest one in the end.
function: f[i] = max(f[i], f[j]+1)，满足j < i， 且nums[j] < nums[i]
initialize: f[0~n-1] = 1
answer: max(f[0~n-1])
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 0; i < nums.length; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
max = Math.max(max, dp[i]);
}
}
}
return max;
}
}
Think further, how to do it using DP with Binary Search?
in this approach, we scan the array from left to right. We also keep a dp array, which is meant to store the increasing subsequence formed by including the currently encountered element. While traversing the nums array, we keep on filling the dp array with the elements encountered so far. 对于elements in jth index(nums[j]), we determine its correct position in the dp array by making use of Binary Search and insert it at the correct position. Note that, we consider only that portion of the dp array in which we have made the updations by inserting some elements at their correct positions(which remains always sorted). Thus, only the elements upto the ith index in the dp array can determine the position of the current element in it.
public class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == len) {
len++;
}
}
return len;
}
}
note: dp: [0 , 2, 12] which is not the longest increasing subsequence, but length of dp array results in length of Longest Increasing Subsequence.
Follow up:
how to get the largest LIS? how to get all the LIS?
Number of Longest Increasing Subsequence
use two array to help solve the problem, one dp array to record the length of the LIS ending in nums[i], and one count array to record the number of the LIS ending in nums[i].
class Solution {
public int findNumberOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
int[] count = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
dp[i] = count[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
if (dp[i] == dp[j] + 1) {
// pay attention: means have another way to reach the same max length increasing sequence
count[i] += count[j]; // important not ++
}
else if (dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
count[i] = count[j];
}
}
}
}
int max_len = 0, res = 0;
for (int num : dp) {
max_len = Math.max(num, max_len);
}
for (int i = 0; i < nums.length; ++i) {
if (dp[i] == max_len) {
res += count[i];
}
}
return res;
}
}
Time complexity is O(n^2) Space complexity is O(n)
Longest Continuous Increasing Subsequence
simple, just two pass scan, dp[i] represents the LCIS ending in nums[i].
class Solution {
public int findLengthOfLCIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else{
dp[i] = 1;
}
}
int res = 1;
for (int num : dp) {
res = Math.max(res, num);
}
return res;
}
}
Longest Increasing Path in a Matrix
similar to the above question, but it extends to a matrix.
So what do you mean by the dp[i][j]?
state: dp[i][j] represent the maximum length of the LIS starting at matrix[i][j] regardless of the direction.
transition function: dp[i][j] = max(dp[i-1][j] , dp[i+1][j], dp[i][j-1], dp[i][j+1])，i, j 都在boundary中，且满足 matrix[i-1][j] > matrix[i][j]..
initialize: dp[i][j] = 0, (0<= i < dp.length, 0 <= j < dp[0].length)
answer: max(dp[i][j])
class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] dp = new int[rows][cols];
int max = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
max = Math.max(max, memorizedSearch(i, j, matrix, dp));
}
}
return max;
}
private int memorizedSearch(int row, int col, int[][] matrix, int[][] dp) {
if (dp[row][col] != 0) return dp[row][col];
for (int[] pair : pairs) {
int x = pair[0] + row;
int y = pair[1] + col;
if (x >= 0 && x < matrix.length &&
y >= 0 && y < matrix[0].length && matrix[x][y] > matrix[row][col]) {
dp[row][col] = Math.max(dp[row][col], memorizedSearch(x, y, matrix, dp));
}
}
return ++dp[row][col];
}
private int[][] pairs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
}
Time complexity: O(mn) Space complexity: O(mn)
or we can use a Topological Sort Based Solution,