html5网站 欣赏,徐州网站推广公司,青少儿编程,浦江网站建设微信开发恭喜你刷到博主 DP 经典题目详解部分第一期#xff0c;想学好 DP 请关注订阅#xff0c;会持续更新#xff01;#xff01;#xff01;#xff01;#xff01;
建议先阅读DP算法入门
00001 最长递增子序列#xff08;Longest Increasing Subsequence#xff0c;简写…恭喜你刷到博主 DP 经典题目详解部分第一期想学好 DP 请关注订阅会持续更新
建议先阅读DP算法入门
00001 最长递增子序列Longest Increasing Subsequence简写 LIS
提要本文介绍两种算法实现
一种是动态规划算法复杂度 On ^ 2
通过本题了解设计动态规划的通用技巧 ———— 数学归纳思想一种是二分查找算法复杂度 On log n
由 patience game 的纸牌游戏甚至有一种排序方法就叫做 patience sorting耐心排序的思想衍生的算法01 动态规划
假设这个结论在 k n 时成立然后想办法证明 k n 的时候此结论也成立。如果能够证明出来那么就说明这个结论对于 k 等于任何数都成立类似的我们设计动态规划算法不是需要一个 dp 数组吗我们可以假设 dp[0...i - 1] 都已经被算出来了怎么通过这些结果算出 dp[i]首先要定义清楚 dp 数组的含义即 dp[i] 的值到底代表着什么
我们的定义是这样的dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
重申一遍 DP 框架
明确状态 - 定义 dp 数组/函数的含义 - 明确选择- 明确 base caseint lengthOfLIS(vectorint nums)
{if (nums.empty())return 0;int n nums.size();//dp 数组应该全部初始化为 1因为子序列最少也要包含自己所以长度最小为 1vectorint dp(n, 1); // 填充 dp 数组for (int i 1; i n; i){//找到前面那些结尾比 i 小的子序列然后把 i 接到最后就可以形成一个新的递增子序列而且这个新的子序列长度加 1for (int j 0; j i; j){if (nums[i] nums[j]){dp[i] max(dp[i], dp[j] 1);}}}// 寻找 dp 数组中的最大值即找最长递增子序列int res 0;for (int i 0; i n; i){res max(res, dp[i]);}return res;
}
10 二分查找
首先我们玩下叫 patience game 的纸牌游戏
规则他的实现原理就是首先使用数组中的第一个数字创建一个纸牌堆然后逐个读取数组中的剩余数字如果当前数字比所有纸牌堆中最上面的数字都大就新建一个纸牌堆把当前数字放到该堆中。否则找到一个最上面数字不小于当前数字的纸牌堆把当前数字放到该纸牌堆中我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗牌堆顶的牌不是有序吗
——— 用到二分查找了搜索当前牌应放置的位置 int LIS(vectorint nums)
{if (nums.empty())return 0;vectorint top; // 用于存储牌堆的顶端元素for (int poker : nums){// 二分查找找到比 poker 大的最小位置auto it lower_bound(top.begin(), top.end(), poker);// 如果没有找到合适的位置说明 poker 应该作为新的牌堆加入if (it top.end()){top.push_back(poker);}else{// 否则更新找到的位置*it poker;}}// 牌堆数即为 LIS 长度return top.size();
} 这里的二分查找直接用了 STL 算法库中的 lower_bound 因为lower_bound 底层实现使用二分查找
想要了解二分查找的实现的参考
template typename ForwardIterator, typename T
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T val) {while (first last) {ForwardIterator mid first (last - first) / 2; // 计算中点if (*mid val) {first mid 1; // 如果 mid 小于 val则搜索右半部分} else {last mid; // 如果 mid 大于或等于 val则搜索左半部分}}return first; // 返回第一个不小于 val 的元素
}
