fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
动态规划设计：最长递增子序列 :: labuladong的算法小抄
咋得到递增子序列呢？这个二分查找最后top数组里面是每堆纸牌最上面的那张牌，牌的堆数就是最长递增子序列长度这个没错，但是好像不太好得到那个最长的递增子序列。求大佬指教。
回復＠Joycn2018
[5,4,3,2,1] 最长递增子序列长度是１ 解集合: [5], [4], [3], [2], [1] 沒有更長的递增子序列了。
最长递增子序列的定義是 Ａ[i] < A[j] for evey i < j
不能頭尾逆著看。
使用数学归纳法的方法, 确定dp代表的含义之后, 在已知dp[:n-1]的情况下, 给出求解dp[n]的方法. 即可迭代的写出动态规划, 这边的action, 貌似并不需要着重考虑
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) 那么dp[0],怎么求，这个循环好像不能进行吧，i=0,j=0,j不＜i
东哥，不知道是我个人总有这个问题，还是共性。 就是，看您的题解，觉得讲得非常清楚，看完立即写也写得很顺。但稍微变一丢丢就又不会了，或者说在有限的时间内大脑一片空白（比如笔试面试的时候）。我觉得只有特别熟练形成肌肉记忆，才有可能在紧张的情况下发挥出平常的水平。 再有就是，您文章中，困难也就是所谓的“坑”，您提前就给我们指好了，看完自然特别顺，但有的点，自己想是想不到的。 比如这篇文章中dp数组的定义，遇到原题说不定能知道这么定义，略微变一点，就想不到定义 以XXX结尾的XXX 啥的。 再比如打家劫舍二，你文中说了分start end讨论那两种情况，就这句话说了就会做了，但关键就在于，如果我是新拿到这道题，我就是想不到您那两种分情况讨论呀。 再比如，最大子数组我会了，那也只是当时会，我笔面试前一两天还刷过，但笔面试变成了最大乘积子数组，我立马写了个模子上去（模子大差不差，细节上不对），但是怎么当时也可能是紧张，大脑一片空白，怎么改都改不对，事后看题解维护两个dp数组，又觉得好简单。但又一次笔试，一道它的变种，但其实比它更简单，我却只能想到复杂些的方法（维护二维数组），想不到这题中那种巧妙的定义方法。 是我还不够熟练吗？可我已经读完所有东哥动态规划的文章了，也做过不止一遍了，呜呜呜~。废话有点多，不知道能不能被东哥翻。
@MathsGo 感谢你把问题描述地这么清楚，我觉得不用失落，这是一个共有的问题。
首先，自己以为自己会了，并不代表真的会了。所以我反复强调看完我的文章后一定要亲去力扣敲代码，哪怕写的一模一样也得自己敲一遍，而不是仅仅复制粘贴过去提交。更进一步，我在 刷题打卡挑战 里要求读者自己输出一遍解题思路，这种输入 + 输出的方式是更有效的学习方式。
另外，面试不仅仅是技术问题，涉及到很多方面的因素，比如你说的紧张导致大脑空白发挥不好，这些都需要多练习，习惯面试的氛围之后就可以更好地展示自己的实力。
最后，任何问题归根结底还是练的不到位，需要勤加练习，多动脑思考，而不是机械性的重复。祝你早日拿到心仪的 offer。
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/ 这个题解的二分查找方法的理解角度也不错~
东哥，不知道是我个人总有这个问题，还是共性。 就是，看您的题解，觉得讲得常清楚，看完立即写也写得很顺。但稍微变一丢丢就又不会了，或者说在有限的时间内大脑一片空白（比如笔试面试的时候）。我觉得只有特别熟练形成肌肉记忆，才有可能在紧张的情况下发挥出平常的水平。 再有就是，您文章中，困难也就是所谓的“坑”，您提前就给我们指好了，看完自然特别顺，但有的点，自己想是想不到的。 比如这篇文章中dp数组的定义，遇到原题说不定能知道这么定义，略微变一点，就想不到定义 以XXX结尾的XXX 啥的。 再比如打家劫舍二，你文中说了分start end讨论那两种情况，就这句话说了就会做了，但关键就在于，如果我是新拿到这道题，我就是想不到您那两种分情况讨论呀。 再比如，最大子数组我会了，那也只是当时会，我笔面试前一两天还刷过，但笔面试变成了最大乘积子数组，我立马写了个模子上去（模子大差不差，细节上不对），但是怎么当时也可能是紧张，大脑一片空白，怎么改都改不对，事后看题解维护两个dp数组，又觉得好简单。但又一次笔试，一道它的变种，但其实比它更简单，我却只能想到复杂些的方法（维护二维数组），想不到这题中那种巧妙的定义方法。 是我还不够熟练吗？可我已经读完所有东哥动态规划的文章了，也做过不止一遍了，呜呜呜~。废话有点多，不知道能不能被东哥翻。
确实是这样子啊，感觉自己的脑子就是想不出来这个规律，变一个题就又被难住了，不知道是不是自己的刷的量还没够，啥时候才能看到第一个题就可以总结出状态转移的规律啊，动态规划的题型真的是太多样了。
@MathsGo 你好真诚哇，我也有这个问题，我觉得这个问题一定是共性的，没有这个问题的选手我都不配做ta的竞争对手😂，所以我就想我只要尽可能的打败我这一层级的人就好了，我做不出的别人（我同层次的）也做不出就好啦。
二分法看不懂的可以看：https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation
超出时间限制 是因为vector太慢了，转成 pair 就好了。
int maxEnvelopes(vector<vector<int>> &envelopes)
{
vector<pair<int,int>> es;
for (auto val: envelopes) es.push_back(make_pair(val[0], val[1])); // 不转成 pair 就过不了
sort(es.begin(), es.end(), [](pair<int, int> a, pair<int, int> b){
return a.first < b.first || (a.first == b.first && a.second > b.second);});
vector<int> dp;
for (auto e : es)
{
auto iter = lower_bound(dp.begin(), dp.end(), e.second);
if (iter == dp.end())
dp.push_back(e.second);
else if (e.second < *iter)
*iter = e.second;
}
return dp.size();
}
我讲一下我对纸牌游戏的理解，因为没有看到证明，所以就想了一下该怎么证
下面假设一个序列分出k个堆。
首先观察到这个序列的最长递增子序列长度不会超过k，证明如下：若原序列存在一个长度为k+1的递增子序列，考虑这个子序列中的元素e[0]<e[1]< ... <e[k]，当e[0]出现时，其会占据一个堆的位置，而当e[1]出现时，其能被放置到的堆必然不同于e[0]所在的堆，因为根据放置规则，e[0]所在的堆当前的牌必然小于等于e[0]，而e[1]>e[0]，同理可得，e[i]放置的堆必然不同于e[0], e[1], ... e[i-1]的堆，即e[0], e[1], ... e[k]所属的堆必然两两不同，故若原序列存在一个长度为k+1的递增子序列，则这个序列必然至少有k+1个堆，与题设矛盾，因此最长递增子序列长度不会超过k。
再证最长递增子序列长度不会小于k，证明思路是从k个堆中构造一个长为k的递增子序列，证明如下：考虑堆产生的过程，按堆生成的顺序给堆编号1,2,...,k，当第k个堆生成时，前k-1个堆必然已经存在，取生成第k个堆时的数作为递增子序列的第k个数，取第k个堆生成时，第k-1个堆堆顶的数为子序列的第k-1个数，需要说明的是，这个数是满足要求的，因为其值必然小于第k个数，不然根据防止规则不可能生成第k个堆，并且显然，这个数在原序列中出现在生成第k个堆的数之前。这样依次取数，即第k-2个数为第k-1个数在放置到第k-1个堆堆顶时第k-2个堆堆顶的数，第i个数为第i+1个数放置到第i+1个堆堆顶时，第i个堆堆顶的数，这些数满足第i个数小于第i+1个数，且第i个数在第i+1个数之前出现，这样，我们构造了一个长度为k的递增子序列，又根据之前部分的证明，在这个序列中不存在长度超过k的最长递增子序列，因此序列的最长递增子序列长度为k
刚刚和同学讨论了分堆后放牌，完全理解了。从思路上说二分不是重点，分堆是重点。只需要明白以下两点：
- 每一张牌一定能和相邻左边堆中的某一张牌构成递增序列（发牌的过程决定的），我们称为一个链路
- 每一堆的牌不能在一个递增序列（链路）中同时出现
以上两点加起来可以保证，分出的堆数就是最长的递增子序列长度。第一点保证有递增链路，第二点保证链路是最长的。
并且最后一堆的牌的个数是最长递增子序列长度的最少组合数。
patience_sort(耐心排序) python verisons
# 比较直观的方式
def lis(nums):
stack = [[]]
for v in nums:
for s in stack:
if not s or s[-1] >= v:
s.append(v)
break
else: # 当前纸牌点数大于当前所有堆的堆顶纸牌点数，新开一堆
stack.append([v])
return len(stack)
# 二分查找
def lis(nums):
n = len(nums)
# 最坏状态是纸牌正序排列，有多少个纸牌拆多少个堆 top数组用于维护所有堆的堆顶最小点数的纸牌
top = [0] * n
piles = 0
for i in range(n):
poker = nums[i]
# left每次都是从0开始，right就是堆的个数，每次的任务就是把当前的poker通过二分查找放进该放的堆中
left, right = 0, piles
while left < right:
mid = (left + right) // 2
if top[mid] > poker: # 当mid位置的纸牌点数≥poker时，当前的poker放入mid左边的堆
right = mid
elif top[mid] < poker: # 放入mid右边的堆
left = mid + 1
else:
right = mid
if left == piles: # 当左边界和堆的个数相同时，需要新开一个堆
piles += 1
top[left] = poker # 更新poker放入的堆顶元素
return piles
这个二分好像和作者的思路不太一样欸
int lengthOfLIS(int[] nums) {
int[] top = new int[nums.length];
// 牌堆数初始化为 0
int piles = 0;
for (int i = 0; i < nums.length; i++) {
// 要处理的扑克牌
int poker = nums[i];
/***** 搜索左侧边界的二分查找 *****/
int left = 0, right = piles;
while (left < right) {
int mid = (left + right) / 2;
if (top[mid] > poker) {
right = mid;
} else if (top[mid] < poker) {
left = mid + 1;
} else {
right = mid;
}
}
/*********************************/
// 没找到合适的牌堆，新建一堆
if (left == piles) piles++;
// 把这张牌放到牌堆顶
top[left] = poker;
}
// 牌堆数就是 LIS 长度
return piles;
}
“牌的堆数就是最长递增子序列的长度，证明略” 看到证明略想了半天，想不出数学正规的证明，用实际想了一下：左小右大，右边新堆之所以出现，就是因为创建新堆的值比前面的堆尾都要大，自然就能形成递增序列。
int lengthOfLIS(int[] nums) {
// 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
int[] dp = new int[nums.length];
// base case：dp 数组全都初始化为 1
Arrays.fill(dp, 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);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
这段可以小优化一下
int lengthOfLIS(int[] nums) {
// 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
int[] dp = new int[nums.length];
// base case：dp 数组全都初始化为 1
Arrays.fill(dp, 1);
int res = 0;
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);
}
res = Math.max(res, dp[i]);
}
return res;
}
// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按宽度升序排列，如果宽度一样，则按高度降序排列
Arrays.sort(envelopes, new Comparator<int[]>()
{
public int compare(int[] a, int[] b) {
return a[0] == b[0] ?
b[1] - a[1] : a[0] - b[0];
}
});
// 对高度数组寻找 LIS
int[] height = new int[n];
for (int i = 0; i < n; i++)
height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
int lengthOfLIS(int[] nums) {
// 见前文
}
排序小优化一下，也省去记忆Comparator
// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按宽度升序排列，如果宽度一样，则按高度降序排列
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
// 对高度数组寻找 LIS
int[] height = new int[n];
for (int i = 0; i < n; i++)
height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
int lengthOfLIS(int[] nums) {
// 见前文
}
这个length of LIS解释比leetcode会员的给的解题思路更通俗易懂，虽然官方答案是耐心排序的简化板，用一维数组（只保留堆顶数）减少空间复杂度。耐心排序的证明和解释很难在面试中完成 尝试写一个尾部开始（自上而下）的子问题动态规划但搞不定
