最长递增子序列问题解法分析！使用动态规划和二分查找实现最长递

发表于

这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战

基本概念

  • 动态规划的通用技巧 : 数学归纳思想
  • 最长递增子序列LIS问题:
    • 动态规划解法. 时间复杂度是 O(N^2^)
    • 二分查找解法. 时间复杂度是 O(Nlog⁡N)O(N\log N)O(NlogN)
  • 注意: 子序列和子串之间的区别
    • 子序列不一定是连续的
    • 子串一定是连续的

动态规划解法

  • 动态规划的核心思想: 数学归纳法
  • 想要证明一个数学结论成立:
    • 先假设这个结论在 k<nk < nk<n 时成立
    • 然后证明 k=nk = nk=n 时此结论也成立
    • 那么就说明这个结论对于 kkk 等于任何数时都是成立的
  • 动态规划算法: 需要一个DP数组
    • 可以假设 dp[0,…,i−1]dp[0,…,i - 1]dp[0,…,i−1] 都已经计算出来
    • 通过这些结果计算出dp[i]dp[i]dp[i]
  • 最长递增子序列LIS问题:
    • 首先要定义清楚 dpdpdp 数组的含义
    • 要清楚 dp[i]dp[i]dp[i] 的值代表的含义
  • 定义: dp[i]dp[i]dp[i] 表示以 nums[i]nums[i]nums[i] 这个数结尾的最长递增子序列的长度
  • 根据定义,可知最终结果的子序列的最大长度就是dp数组中的最大值
1
2
3
4
5
c复制代码int res = 0;
for (int i = 0; i < dp.size(); i ++) {
	res = Math.max(res, dp[i]);
}
return res;

  • 设计动态规划算法正确计算每个 dp[i]dp[i]dp[i] : 使用数学归纳法思考如何进行状态转移

    • 根据对dp数组的定义,已知 dp[0,…,4]dp[0,…,4]dp[0,…,4] 的结果,要求 dp[5]dp[5]dp[5] 的值,也就是要求 nums[5]nums[5]nums[5] 为结尾的最长递增子序列

    • nums[5]=3nums[5]=3nums[5]=3,因为是递增子序列,只要找到之前结尾比3小的递增子序列,然后将3接到最后,就可以形成一个新的递增子序列,并且这个新的序列长度会增加1

    • 形成的子序列有多种,只是需要最长的,将最长子序列的长度作为 dp[5]dp[5]dp[5] 的值

      1
      2
      3
      4
      5
      c复制代码for (int j = 0; j < i, j++) {
      	if (nums[i] > nums[j]) {
      		dp[i] = Math.max(dp[i], dp[j] + 1);
      	}
      }

    • 使用数学归纳法,可以计算出其余的dp数组的值

      1
      2
      3
      4
      5
      6
      7
      c复制代码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数组应该全部初始化为1, 因为子序列长度最少也要包含自己,所以最小长度为1而不为0

  • 最长递增子序列完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码public int lengthOfLIS() {
	int[] dp = new int[nums.length];
	// 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;
}
  • 最长递增子序列的DP数组算法的时间复杂度为O(N^2^)
  • 动态规划设计流程:
    • 首先明确DP数组所存数据的含义
      • 这步很重要,如果含义不明确,会导致后续步骤计算混乱
    • 然后根据DP数组的定义,计算出 dp[i]dp[i]dp[i]
      • 运用数学归纳法的思想,假设 dp[0,…,i−1]dp[0,…,i-1]dp[0,…,i−1] 的值都是已知,根据 dp[0,…,i−1]dp[0,…,i-1]dp[0,…,i−1] 的值求出 dp[i]dp[i]dp[i]
        • 一旦完成这个步骤,整个题目就基本解决了
        • 如果无法完成这一步骤,就要重新思考DP数组的定义
        • 或者可能是DP数组存储的信息不完全,无法推导出下一步的答案,就需要将DP数组扩大成为二维数组甚至三维数组
    • 最后确定问题的base case
      • 使用base case初始化数组,保证算法正确运行

二分查找解法

  • 最长递增子序列的二分查找解法的算法时间复杂度为 O(Nlog⁡N)O(N\log N)O(NlogN)
  • 最长递增子序列和一种叫作patience game的纸牌游戏有关,有一种排序算法就叫做耐心排序patience sorting
  • 场景分析: 给定一排纸牌,然后从左到右像遍历数组那样一张一张处置这些纸牌,最终将这些纸牌分成若干堆
    • 只能将点数小的牌压到点数大的牌上
    • 如果当前牌点数较大没有可以放置的堆,则新建一个堆,将这张牌放置进去
    • 如果当前牌有多个堆可供选择,则选择最左边的堆放置
      • 选择最左边的堆放置的原因是为了保证堆顶的牌有序
  • 按照上述规则,可以算出最长递增子序列,牌堆数就是最长递增子序列的长度
  • 二分查找算法求解最长递增子序列:
    • 将处理扑克牌的过程使用编程的方式表达出来
    • 因为每次处理一张扑克牌要找到一个合适的牌堆顶放置,牌堆顶的牌是有序的.所以可以使用二分查找
    • 使用二分查找来搜索当前牌应该放置的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
c复制代码public 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 -left) / 2;
			if (top[mid] > poker) {
				right = mid;
			} else if (top[mid] < poker) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		// 没有找到合适的牌堆则新建一个牌堆
		if (left == piles) {
			piles++;
		}
		// 选择最左边的牌堆放置
		top[left] = piles;
	}
	// 牌堆数就是最长递增子串的长度
	return piles;
}
  • 二分查找解法:
    • 首先涉及数学证明,要证明出按照这些规则的执行,就能得到最长递增子序列
    • 其次是二分查找算法的应用,要理解二分查找方法的细节
  • 动态规划设计方法:
    • 假设之前的答案为已知
    • 利用数学归纳法的思想正确进行状态转移
    • 最后得到答案
  • 动态规划解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
> python复制代码def lengthOfLIS(self, nums : List[int]) -> int:
> 	n = len(nums)
> 	dp = [1 for x in range(0, n)]
> 	for i in range(0, n):
> 		for j in range(0, i):
> 			if nums[i] > num[j]:
> 				dp[i] = max(dp[i], dp[j] + 1)
> 	res = 0
> 	for temp in dp:
> 		res = max(temp, res)
> 	return res
> 
>
  • 二分查找解法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
> python复制代码def lengthOfLIS(self, nums : List[int]) -> int:
> 	top = []
> 	# 牌堆初始化为0
> 	piles = 0
> 	# num为需要处理的牌
> 	for num in nums:
> 		left, right = 0, 
>   while left < right:
>   	mid = left + (right - left) / 2
>   	# 搜索左侧边界
>   	if top[mid] > num:
>   		right = mid
>   	# 搜索右侧边界
>   	elif top[mid] < num:
>   		left = mid + 1
>   	else
>   		right = mid
>   if left == piles:
>   	# 如果没有找到合适的牌堆,就新建一个牌堆
>   	piles += 1
>   # 将该牌放到新建的牌堆顶
>   top[left] = num
>   # 牌堆数就是最长递增子序列的长度
>   return piles
> 
>

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%