|
这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战
基本概念
动态规划的通用技巧 : 数学归纳思想
最长递增子序列LIS问题:
动态规划解法. 时间复杂度是 O(N^2^)
二分查找解法. 时间复杂度是 O(NlogN)O(N\log N)O(NlogN)
注意: 子序列和子串之间的区别
子序列不一定是连续的
子串一定是连续的
动态规划解法
动态规划的核心思想: 数学归纳法
想要证明一个数学结论成立:
先假设这个结论在 k nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
dp数组应该全部初始化为1, 因为子序列长度最少也要包含自己,所以最小长度为1而不为0
最长递增子序列完整代码:
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(NlogN)O(N\log N)O(NlogN)
最长递增子序列和一种叫作patience game的纸牌游戏有关,有一种排序算法就叫做耐心排序patience sorting
场景分析: 给定一排纸牌,然后从左到右像遍历数组那样一张一张处置这些纸牌,最终将这些纸牌分成若干堆
只能将点数小的牌压到点数大的牌上
如果当前牌点数较大没有可以放置的堆,则新建一个堆,将这张牌放置进去
如果当前牌有多个堆可供选择,则选择最左边的堆放置
选择最左边的堆放置的原因是为了保证堆顶的牌有序
按照上述规则,可以算出最长递增子序列,牌堆数就是最长递增子序列的长度
二分查找算法求解最长递增子序列:
将处理扑克牌的过程使用编程的方式表达出来
因为每次处理一张扑克牌要找到一个合适的牌堆顶放置,牌堆顶的牌是有序的.所以可以使用二分查找
使用二分查找来搜索当前牌应该放置的位置
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;
}
二分查找解法:
首先涉及数学证明,要证明出按照这些规则的执行,就能得到最长递增子序列
其次是二分查找算法的应用,要理解二分查找方法的细节
动态规划设计方法:
假设之前的答案为已知
利用数学归纳法的思想正确进行状态转移
最后得到答案
动态规划解法:
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
二分查找解法:
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
|