动态规划与二分法破解最长递增子序列
LeetCode300
给你一个整数数组nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
Python解法
1.动态规划
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if len(nums) == 0: return 0 dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)2.贪心+二分
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: d = [] for num in nums: # 直接二分查找第一个 >= num 的位置 left, right = 0, len(d) while left < right: mid = (left + right) // 2 if d[mid] >= num: right = mid else: left = mid + 1 # left就是要替换的下标 if left == len(d): d.append(num) else: d[left] = num return len(d)Java解法
1.动态规划
class Solution { public int lengthOfLIS(int[] nums) { if(nums.length == 0) return 0; int[] dp = new int[nums.length]; for(int i = 0; i < nums.length; i++){ dp[i] = 1; } int res = 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); } } res = Math.max(res, dp[i]); } return res; } }2.贪心+二分
class Solution { public int lengthOfLIS(int[] nums) { int[] d = new int[nums.length]; int len = 0; for (int num : nums) { int left = 0, right = len; while (left < right) { int mid = (left + right) / 2; if (d[mid] >= num) { right = mid; } else { left = mid + 1; } } if (left == len) { d[len++] = num; } else { d[left] = num; } } return len; } }C++解法
1.动态规划
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n == 0)return 0; vector<int> dp(n, 1); // 初始化dp数组，所有元素初始值为1 for (int i = 0; i < n; ++i) { // 遍历i之前所有元素 j ∈ [0, i-1] for (int j = 0; j < i; ++j) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); } } } // 返回dp数组最大值 return *max_element(dp.begin(), dp.end()); } };2.贪心+二分
class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> d; for (int num : nums) { int left = 0, right = d.size(); while (left < right) { int mid = (left + right) / 2; if (d[mid] >= num) { right = mid; } else { left = mid + 1; } } if (left == d.size()) { d.push_back(num); } else { d[left] = num; } } return d.size(); } };一、动态规划 DP
原理
- 拆分成小问题，存下每个小问题的最优解，避免重复计算；
- 靠前面结果推出当前结果，满足：最优子结构、重叠子问题、无后效性。
LIS 里的表现
dp[i]：以第 i 个数结尾的最长递增子序列长度，逐个对比前面所有数字更新。
复杂度
\(O(n^2)\)
适合题目
- 数据量小（n≤1000）；
- 需要输出完整子序列、统计有多少条最长序列；
- 背包、最长公共子序列 LCS、打家劫舍、股票问题（贪心做不了）。
二、贪心 + 二分（LIS 优化版）
原理
- 贪心：相同长度的递增子序列，末尾数字越小，后续越好接更大数字；
- 二分：快速找到要替换的位置，把时间压到对数级。
LIS 里的表现
数组 d：d [k] 代表长度 k+1 的序列最小末尾值，新数字要么加长序列，要么替换旧末尾。
复杂度
\(O(n\log n)\)
适合题目
- 数据量大（n 上万 / 十万）；
- 只需要求最长序列长度，不需要路径、计数；
- 导弹拦截、俄罗斯套娃信封。
极简区分
- DP：万能，能计数 / 找路径，慢，小数组用；
- 贪心二分：只算长度，速度极快，大数据专用。