接龙型DP
300. Longest Increasing Subsequence
关键题来了，动规经典问题。
先从 O(n^2) 的 DP 做法说起。先从这个开做，是因为 O(n^2) 做法的普适性高，而且可以无视维度，易于扩展到各种变形与 follow-up 上。
将n个数看做n个木桩, 目的是从某个木桩出发, 从前向后, 从低往高, 看做多能踩多少个木桩。
没有明确的起终点。必须是严格递增。
- state: f[i] 表示(从任意某个木桩)跳到第i个木桩, 最多踩过多少根木桩
- function: f[i] = max{f[j] + 1}, j必须满足 j < i && nums[j] < nums[i]
- initialize: f[0 .. n - 1] = 1
- answer: max{f[0 .. n - 1]}
容易想错，容易把这道题做成单序列的动规问题。
public class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] f = new int[n];
for (int i = 0; i < n; ++i) {
f[i] = 1;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
}
int max = 0;
for (int i = 0; i < n; ++i) {
max = Math.max(max, f[i]);
}
return max;
}
}
这道题的 follow-up 是降低时间复杂度，动规的复杂度是 n^2. Binary Search来做是 nlogn。
354. Russian Doll Envelopes
Hard题。上一道题的变形，俄罗斯套娃。
[[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]
这题试着用 LIS 的写法思路写了一下，然而卡在了这个 test case 上。
因为这题，元素之间不存在绝对的大小，不能直接用两个 tuple 去比较，进行 binary search.
两个 tuple [4,300] 和 [5,250] 之间，按理可以说 [4, 300] 更小，但是有可能最优解是由 [5,250] 选出来的。
正解的流程：
按 [w, h] 中的 w 升序排序；
如果 w 相等，则按照 h 的降序排序(重要！！！)
后面的就和一维 LIS 一样，只考虑 h 的维度做 LIS 就行了。
难点在于，为什么这么做是正确的？
不难看出对于同一个 w 的楼层，我们不能按 h 升序排列，因为会延长自身，导致在同一个 w 上多次套用。
因此对于同一 w 的情况， 要按照 h 降序排列
这样当我们看到一个更大的 h 时，我们可以确定，这一定是一个新的 w，而且根据原来排序的单调性，一定是一个比单调栈内元素都大的新 w，可以套上。
同时对于单调栈中的任意 h，如果 binary search 之后的位置 pos 位于中间，它一定可以套在 pos 之前的所有信封上。
public class Solution {
private class MyComparator implements Comparator<int[]>{
public int compare(int[] a, int[] b){
if(a[0] != b[0]) return (a[0] < b[0]) ? -1: 1;
else return (a[1] < b[1]) ? 1: -1;
}
}
public int maxEnvelopes(int[][] envelopes) {
if(envelopes == null || envelopes.length == 0) return 0;
Arrays.sort(envelopes, new MyComparator());
int n = envelopes.length;
int[] dp = new int[n];
dp[0] = envelopes[0][1];
int index = 0;
for(int i = 1; i < n; i++){
int pos = binarySearch(dp, 0, index, envelopes[i][1]);
if(pos > index){
dp[pos] = envelopes[i][1];
index = pos;
}
dp[pos] = Math.min(dp[pos], envelopes[i][1]);
}
return index + 1;
}
private int binarySearch(int[] dp, int start, int end, int height){
int left = start;
int right = end;
while(left + 1 < right){
int mid = left + (right - left) / 2;
if(height < dp[mid]){
right = mid;
} else {
left = mid;
}
}
if(height <= dp[left]) return left;
if(height > dp[right]) return right + 1;
return right;
}
}
368. Largest Divisible Subset
这个文章讲的不错。
长的和 LIS 的 O(n^2) DP 解法很像。
这题正确性的保证：对于排序数组 nums 的两个 index，i, j 并且 j < i 的情况下，如果 nums[i] % nums[j] == 0，那么包含 nums[j] 的 subset 里所有元素也一定能整除 nums[i]. 因为 nums[j] 是其 subset 中当前最大的元素，而且一定可以整除所有比它小的。
主要不同点：
因为最后要输出结果，得存个 parent 数组记录每个序列的前一个元素
每次往回扫的时候，不能像 LIS 那样看到大的就停手，要走到底
这么讲的话，貌似要输出具体 LIS 序列的题，也可以这么做。。O(n^2) 时间，O(n) 空间就可以了。
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> rst = new ArrayList<>();
if(nums == null || nums.length == 0) return rst;
Arrays.sort(nums);
int[] dp = new int[nums.length];
int[] parent = new int[nums.length];
Arrays.fill(dp, 1);
Arrays.fill(parent, -1);
int maxIndex = -1;
int maxLen = 1;
for(int i = 0; i < nums.length; i++){
for(int j = i - 1; j >= 0; j--){
if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
parent[i] = j;
if(dp[i] > maxLen){
maxLen = dp[i];
maxIndex = i;
}
}
}
}
if(maxIndex == -1){
rst.add(nums[0]);
} else {
while(maxIndex != -1){
rst.add(nums[maxIndex]);
maxIndex = parent[maxIndex];
}
}
return rst;
}
}