动态规划设计：最长递增子序列 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：动态规划设计：最长递增子序列

评论礼仪 见这里，违者直接拉黑。

[xiaoye-2018]

二分杀我

[laoyoutiao237]

以下来自高畅 Leetcode101中对最长递增子序列的解释:

本题还可以使用二分查找将时间复杂度降低为 O(n log n)。我们定义一个 dp 数组，其中 dp[k]存储长度为k+1的最长递增子序列的最后一个数字。我们遍历每一个位置 i，如果 其对应的数字大于dp数组中所有数字的值，那么我们把它放在 dp 数组尾部，表示最长递增子序列长度加 1；如果我们发现这个数字在dp数组中比数字a大、比数字 b 小，则我们将b更新为此数字，使得之后构成递增序列的可能性增大。以这种方式维护的dp数组永远是递增的，因此可以用二分查找加速搜索。

int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return n;
vector<int> dp;
dp.push_back(nums[0]);
for (int i = 1; i < n; ++i) {
if (dp.back() < nums[i]) {
dp.push_back(nums[i]);
} else {
auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);
*itr = nums[i];
}
}
return dp.size();

[llnancy]

咋得到递增子序列呢？这个二分查找最后top数组里面是每堆纸牌最上面的那张牌，牌的堆数就是最长递增子序列长度这个没错，但是好像不太好得到那个最长的递增子序列。求大佬指教。

[masterX89]

贪心算法或者说 patience game 只会保留当前长度的 LIS 下的末尾最小元素，

所以如果需要记录最长递增子序列的话，需要使用一个 path 辅助数组

path[i] 存放了到达当前的 numsI 的 prevIndex，即 贪心+二分+路径回溯。

之前看 vue 的源码时候手撕了一个 demo，可以参考一下：

function getSequence(nums: number[]): number[] {
  const path = nums.slice()
  let d = [0]
  for (let i = 1; i < nums.length; i++) {
    const numsI = nums[i]
    if (numsI > nums[d[d.length - 1]]) {
      // 记录路径
      // 是由当前的 d 末尾索引指向的元素到达的 numsI
      path[i] = d[d.length - 1]
      d.push(i)
    } else {
      let l = 0
      let r = d.length - 1
      while (l <= r) {
        let mid = (l + r) >> 1
        if (numsI > nums[d[mid]]) {
          l = mid + 1
        } else {
          r = mid - 1
        }
      }
      // 记录路径
      // 使用 i 覆盖 d[l]
      // 因此记录 path[i] 上一个索引为 d[l - 1]
      path[i] = d[l - 1]
      d[l] = i
    }
  }
  // 反向恢复出正确的 LIS 索引数组
  let prev = d[d.length - 1]
  for (let i = d.length - 1; i >= 0; i--) {
    d[i] = prev
    // 通过 path 返回上一个 index
    prev = path[prev]
  }
  return d
}

[hprof]

agree that: "正常人基本想不到这种解法"

[Joycn2018]

二分法没太懂，牌的堆数就是最长递增子序列长度，如果原序列是 [5,4,3,2,1]，则牌堆数为1，不等于最长递增子序列长度呀？

[StefanJava]

为啥不等于

[zhangmuwuge]

老铁 递增！肯定不等于

[brianchiang-tw]

回復＠Joycn2018

[5,4,3,2,1] 最长递增子序列长度是１
解集合: [5], [4], [3], [2], [1]
沒有更長的递增子序列了。

最长递增子序列的定義是
Ａ[i] < A[j] for evey i < j

不能頭尾逆著看。

[JackShang94]

二分法这堆牌让我想起了老windows游戏，“空当接龙”。不过规则略有改变

[deepbreath373]

和蜘蛛纸牌也有点像

[Asber777]

使用数学归纳法的方法, 确定dp代表的含义之后, 在已知dp[:n-1]的情况下, 给出求解dp[n]的方法. 即可迭代的写出动态规划, 这边的action, 貌似并不需要着重考虑

[huangpan2507]

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

[diandengpao]

dp[0] 是底 等于1

[MathsGo]

东哥，不知道是我个人总有这个问题，还是共性。
就是，看您的题解，觉得讲得非常清楚，看完立即写也写得很顺。但稍微变一丢丢就又不会了，或者说在有限的时间内大脑一片空白（比如笔试面试的时候）。我觉得只有特别熟练形成肌肉记忆，才有可能在紧张的情况下发挥出平常的水平。
再有就是，您文章中，困难也就是所谓的“坑”，您提前就给我们指好了，看完自然特别顺，但有的点，自己想是想不到的。
比如这篇文章中dp数组的定义，遇到原题说不定能知道这么定义，略微变一点，就想不到定义 以XXX结尾的XXX 啥的。
再比如打家劫舍二，你文中说了分start end讨论那两种情况，就这句话说了就会做了，但关键就在于，如果我是新拿到这道题，我就是想不到您那两种分情况讨论呀。
再比如，最大子数组我会了，那也只是当时会，我笔面试前一两天还刷过，但笔面试变成了最大乘积子数组，我立马写了个模子上去（模子大差不差，细节上不对），但是怎么当时也可能是紧张，大脑一片空白，怎么改都改不对，事后看题解维护两个dp数组，又觉得好简单。但又一次笔试，一道它的变种，但其实比它更简单，我却只能想到复杂些的方法（维护二维数组），想不到这题中那种巧妙的定义方法。
是我还不够熟练吗？可我已经读完所有东哥动态规划的文章了，也做过不止一遍了，呜呜呜~。废话有点多，不知道能不能被东哥翻。

[Drome586]

zantong

[llxblhyvia]

这几篇文章列出来的就跟“课本例题”一样吧，能学过课本例题就能考试时候做出来变式题的人也有，不过大部分人不都还得再补充做很多习题才能真正掌握嘛，共勉了兄弟！

[labuladong]

@MathsGo 感谢你把问题描述地这么清楚，我觉得不用失落，这是一个共有的问题。

首先，自己以为自己会了，并不代表真的会了。所以我反复强调看完我的文章后一定要亲去力扣敲代码，哪怕写的一模一样也得自己敲一遍，而不是仅仅复制粘贴过去提交。更进一步，我在 刷题打卡挑战 里要求读者自己输出一遍解题思路，这种输入 + 输出的方式是更有效的学习方式。

另外，面试不仅仅是技术问题，涉及到很多方面的因素，比如你说的紧张导致大脑空白发挥不好，这些都需要多练习，习惯面试的氛围之后就可以更好地展示自己的实力。

最后，任何问题归根结底还是练的不到位，需要勤加练习，多动脑思考，而不是机械性的重复。祝你早日拿到心仪的 offer。

[Alex43975]

俄罗斯套娃那道题 用DP的解法写LIS过不了 力扣给的测试样例太变态了 超出时间限制了

[yangyj1994]

图一dp[2]是不是画错了，按图解应该是dp[4]

[labuladong]

@StrawHat-YYJ 确实画错了，感谢指出，我改下

[shoren0305]

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/ 这个题解的二分查找方法的理解角度也不错~

[morganwu277]

链接中的解法2，其本质是，贪心而非DP

[douglasdotc]

Hi, thanks for the detailed explanation! This article definitely improves my understanding about dynamic programming (DP) :D
For the LIS problem, I think I found an O(n) time, O(n) space solution. Strictly speaking I don't think my solution is DP as it uses a monotonic stack. My idea is to keep an increasing monotonic stack and track its length since we do not need the increasing length for each element but for the array as a whole:

def LIS(nums):
	if len(nums) == 0:
		return 0

	res = 0
	stack = []
	for n in nums:
		while len(stack) > 0 and n < stack[-1]:
			stack.pop()
		if len(stack) == 0 or (len(stack) > 0 and n > stack[-1]):
			stack.append(n)
		res = max(res, len(stack))
	return res

tests = [
	[1,4,3,4,2,3], #3
	[1,2,3,4,5,6], #6
	[1,1,1,1,1,1], #1
	[6,5,4,3,2,1], #1
	[6,5,4,1,2,3]  #3
]

for test in tests:
	print(LIS(test))

[douglasdotc]

turns out it was wrong, please ignore :/

[jeff-wangzhen]

为什么信封那个问题，“如果遇到 w 相同的情况，则按照高度 h 降序排序”呢？h 也升序有什么问题吗？

[KitherRunner]

如果height是升序的话，就不能只看height了，需要同时关注width和height，例如：[[1, 2], [1, 3]]
height降序保证了在不看width的情况下，height选取的肯定是唯一的，对于同一个width而言

[jeff-wangzhen]

如果height是升序的话，就不能只看height了，需要同时关注width和height，例如：[[1, 2], [1, 3]] height降序保证了在不看width的情况下，height选取的肯定是唯一的，对于同一个width而言

@KitherRunner 没懂。。题目说了长宽都要更大才能套，所以不可能不看width；其次，为什么降序可以保证不看width的情况下保证height唯一呢？比如 [[1,1], [1,2], [1,3],[2,1], [2,2], [2,3]]，选定[1,1],后面只能选[2,2]或[2,3],选定[1,2],后面只能选[2,3]，选[1,3]后面都不能套，就3种套法，信封最多2个。height降序就是[[1,3],[1,2],[1,1],[2,3],[2,2],[2,1]]，选定[1,3]后面都不能套，选定[1,2],后面只能选[2,3]，选定[1,1],后面只能选[2,3]或[2,2], 感觉没啥区别。。

[KitherRunner]

如果height是升序的话，就不能只看height了，需要同时关注width和height，例如：[[1, 2], [1, 3]] height降序保证了在不看width的情况下，height选取的肯定是唯一的，对于同一个width而言

@KitherRunner 没懂。。题目说了长宽都要更大才能套，所以不可能不看width；其次，为什么降序可以保证不看width的情况下保证height唯一呢？比如 [[1,1], [1,2], [1,3],[2,1], [2,2], [2,3]]，选定[1,1],后面只能选[2,2]或[2,3],选定[1,2],后面只能选[2,3]，选[1,3]后面都不能套，就3种套法，信封最多2个。height降序就是[[1,3],[1,2],[1,1],[2,3],[2,2],[2,1]]，选定[1,3]后面都不能套，选定[1,2],后面只能选[2,3]，选定[1,1],后面只能选[2,3]或[2,2], 感觉没啥区别。。

最终方法：width升序、height降序情况下的heigth最长递增子序列
width和heigth升序：
[[1,1], [1,2], [1,3],[2,1], [2,2], [2,3]]：按照height升序，当选定了第一个[1,1]之后[1,2],[1,3]还是需要进行判断（因为height是递增的，只是因为width一致才导致了不能选择），同理后面的[2,1],[2,2],[2,3]同样要进行判断，此时可以看出不能忽略 width 和 height 中的任何一个

width升序、height降序：
[[1,3],[1,2],[1,1],[2,3],[2,2],[2,1]]：按照height降序，此时同一width的height是降序的，所以对于width而言，每次肯定只能其中选择一个 （我们找的是height的递增子序列），并且选到的下一个height，width肯定是不同的，相当于保证了不看width，只看height的情况下，结果也是正确的（因为选到的两个height对应的 width 肯定是不同的（选择的height是升序，而同一width的height是降序，必然是冲突的））。

[yangrenmu]

h升序的话,[5,2]可以放[5,4]里面。但是显然是不能放进去的，因为宽度相同。

[wuhaidu]

w 相同的情况，h应该是只能降序。 如果升序，最后得到的h集合里面，递增序列就会存在w相同的h，跟题目冲突了。如果是降序，就不会存在这样的情况，因为w相同的h本身是降序的，不会存在递增序列。

[CharmSea]

最长递增自序列 中的 动态规划 解法有一些疑问，希望给位大佬可以帮忙解答一下

按照 明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义 这个思维框架来梳理，那么

base case: dp[i] 初始值为1
状态: 以 nums[i] 结尾的最长子序列
选择: 数学归纳法
dp[i]数组的下标: 以 nums[i] 结尾的子序列
dp[i]数组的元素: 以 nums[i] 结尾的子序列长度

是这样理解吗？

[qweasd54]

最长递增子序列那个二分法中第三个else是为什么，想不明白

[miiiiiko]

记录下为什么牌的堆数就是最长递增子序列。

首先，先证明最长递增子序列长度大于等于牌的堆数。每次把牌放到第二堆以后的堆，都一定是因为它在前一堆放不上去，也就是是说大于前一堆的最顶上的牌，因此可以记录个指针，指向放这张牌时的上一堆的最后一张牌，最后从最后一堆的一张牌出发，顺着指针可以一直走到第一堆，把这几张牌挑出来，肯定是按顺序且递增的。因此找到了一个长度为堆数的递增子序列。

假设最长递增子序列的长度大于堆数，那么必有两个牌会在一个牌堆，而且先放下去的底下的牌反而比较小，与规则不符，所以最长递增子序列长度不超过牌堆数。

综上，牌堆数必是最长递增子序列的长度。

[xshu216]

为什么不可以这样去做呢

for(int i = 0;i<sz;i++){
            for(int k = i+1;k<sz;k++){

[newlifehaonan]

Top down dp 函数递归解法

    public int lengthOfLIS(int[] nums) {
        int[] memo = new int[nums.length];
        if (nums.length == 0) return 0;
        Arrays.fill(memo, -1);
        dp(nums, nums.length - 1, memo);
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int sub = dp(nums, i, memo);
            res = Math.max(res, sub);
        }
        return res;
    }

    // 定义dp函数的状态，dp(i) 代表 index 在 i 处最长递增子序列的个数
    // 状态转移方程: nums[i] > nums[j], j 为 j < i 的所有取值，result = max(result, dp(j) + 1));
    // base case, dp(0) = 1;
    // 备忘录起始值为-1;

    public int dp(int[] nums, int i, int[] memo) {
        if (i == 0) return 1;
        if (memo[i] > 0) return memo[i];
        int res = 1;
        for (int j = i - 1; j >= 0; j--) {
            if(nums[j] < nums[i]) {
                res = Math.max(res, dp(nums, j, memo) + 1);
            }
        }
        memo[i] = res;
        return  (memo[i] != -1) ? memo[i] : -1;
    }

[WenLexiao]

俄罗斯套娃信封过不了测试用例(c++)，原因是排序规则写错了，应该改为：

sort(envelopes.begin(), envelopes.end(),
     [](vector<int>& a, vector<int>& b) { 
           return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]); 
      });

[zenyanggongmian1995]

for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
// 寻找 nums[0..j-1] 中比 nums[i] 小的元素
if (nums[i] > nums[j]) {
// 把 nums[i] 接在后面，即可形成长度为 dp[j] + 1，
// 且以 nums[i] 为结尾的递增子序列
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}

@labuladong 这里应该是寻找/ 寻找 nums[0..i-1] 中比 nums[i] 小的元素的元素吧。

[PPPcodeTry]

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
我用这个例子 int[]{10,9,2,5,3,7,101,18,6} 跑了一下二分查找法，最长子序列长度是正确的4，而 top 数组内容变成了[2, 3, 6, 18, 0, 0, 0, 0, 0]，6应该在18之后，如果要打印子序列，这个用例就没法通过

[RomeoFourier]

感觉二分法那里有个地方说的不对：“只能把点数小的牌压到点数比它大的牌上”。事实上可以压在点数相等的牌上，否则俄罗斯套娃的第二个用例三个1会出现三个堆，但东哥的示例代码是正确的，和描述的不一样

[wuzeyu2015]

纯粹用回溯来求解300.最长递增子序列，是不是就没办法优化了？

var max int
var res []int

func lengthOfLIS(nums []int) int {
    max = -1
    res = make([]int, 0)
    backtrace(nums, 0)
    return max
}

func backtrace(nums []int, i int) {
    if max < len(res) {
        max = len(res)
    }
    if i >= len(nums) {
        return
    }
    if len(res) == 0 {
        res = append(res, nums[i])
        backtrace(nums, i+1)
        res = res[:len(res)-1]
        backtrace(nums, i+1)
    } else if res[len(res)-1] < nums[i] {
        res = append(res, nums[i])
        backtrace(nums, i+1)
        res = res[:len(res)-1]
        backtrace(nums, i+1)
    } else {
        backtrace(nums, i+1)
    }
}

[wuzeyu2015]

超出时间限制
22 / 54 个通过的测试用例

[jjkksstt]

醍醐灌顶，顶礼膜拜，比澳洲某top讲的清楚多了

[chl64]

对 300. 最长递增子序列，Youtube 有从“暴力解”开始讲起的题解，分享给其他小伙伴参考：
https://www.youtube.com/watch?v=cjWnW0hdF1Y

[Eunice-grow]

二分法那里为什么top[mid]== poker时right = mid呢，还有为什么新建牌堆的时机时left==piles，一直没想明白