【算法面试入门必刷】动态规划-线性dp（四）
- 前言
- 算法入门刷题训练
- 题目AB37：最长上升子序列(一)
- 题目分析
- 理论准备
- 题解
- 小结
📦个人主页：一二三o-0-O的博客
🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑）
👨💻作者简介：数据结构算法与音视频领域创作者
📒 系列专栏：牛客网面试必刷
📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer
📝推荐一个找工作神器：牛客刷题网 【面试经验|实习招聘内推，求职就业一战解决】
🧡如果对您有帮助的话，欢迎点赞👍收藏📂，关注不迷路
【算法入门必刷】数据结构-栈篇系列文章：
【算法入门必刷】数据结构-栈（一）
【算法入门必刷】数据结构-栈（二）
【算法入门必刷】数据结构-栈（三）
【算法入门必刷】数据结构-栈（四）
【算法入门必刷】数据结构-栈（五）
【算法入门必刷】动态规划-线性dp篇系列文章：
【算法面试入门必刷】动态规划-线性dp（一）
【算法面试入门必刷】动态规划-线性dp（二）
【算法面试入门必刷】动态规划-线性dp（三）
前言
开启刷题，请点击右边链接进行跳转点击这里
算法入门刷题训练
题目AB37：最长上升子序列(一)
题目分析
描述
给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i 和 j 满足 i<j 且 arr i ≥ arr j.
这道题目与上一篇【算法面试入门必刷】动态规划-线性dp（三）中练习的连续子数组最大和有个不同就是，要求的子数组不是连续的。因此可以定义动态规划数组dp[i] 表示以第i个数字为结尾的最长连续子序列的长度。从而推导出递推公式：dp[i] = maxLength + 1，其中maxLength表示从下标0到i-1中dp数组最大值（最大的连续子序列的长度）。
理论准备
任何算法都有相对应的算法模板或者有规律的解题步骤。对于动态规划来讲，做DP相关的算法题要熟练掌握下面DP解题步骤，这样有助于在面对到各种各样的题目时能够提高解题效率：
DP解题步骤:
- 首先要确定dp数组：是一维，二维还是三维；以及下标的含义是什么？
- 根据确定好的dp数组，给出递推公式，也叫状态转移方程。
- 确定dp数组是否需要初始化，初始化为多少。
- 确定遍历的顺序；这一步在背包相关的DP题目中非常重要。
- 根据测试用例进行验证
题解
具体的解决方案如下：
- 首先确定dp数组：是一维，二维还是三维；以及下标的含义是什么？
// 这里使用一维dp
// dp[i] 表示以第i个数字为结尾的最长连续子序列的长度
vector<int> dp(n);
- 根据确定好的dp数组，给出递推公式。
// 根据题目分析得出了以下递推公式：
// dp[i] = maxLength + 1，其中maxLength表示从下标0到i-1中dp数组最大值（当前值之前的最大的连续子序列的长度）。
int maxValue{};
// 求得从下标0到下标i-1中dp值的最大值
for(int j{};j<i;++j){
// 当当前值大于v[j]，才进行dp[j]的判断
if(v[i] > v[j]){
maxValue = max(maxValue,dp[j]);
}
}
// 然后dp[i]就等于之前的最大的连续子序列的长度加上当前数值
dp[i] = maxValue + 1;
- 确定dp数组是否需要初始化，初始化为多少。
// 根据dp[i]的定义，子序列的最短长度都是本身即1
vector<int> dp(n,1);
- 确定遍历的顺序；这一步在背包相关的DP题目中非常重要。
// 本题从小到大遍历i
for(int i{1};i<n;++i){
int maxValue{};
// 内部从小到大，从大到小都可以
for(int j{};j<i;++j){
if(v[i] > v[j]){
maxValue = max(maxValue,dp[j]);
}
}
}
-
根据测试用例进行验证：选择所有的测试用例带入验证即可。
-
完整代码如下：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for(int i{};i<n;++i) cin >> v[i];
// dp[i] 表示以第i个数字为结尾的最长连续子序列的长度
vector<int> dp(n,1);
int result{};
for(int i{1};i<n;++i){
int maxValue{};
for(int j{};j<i;++j){
if(v[i] > v[j]){
maxValue = max(maxValue,dp[j]);
}
}
dp[i] = maxValue + 1;
if(dp[i] > result) result = dp[i];
}
cout << result << endl;
return 0;
}
// 64 位输出请用 printf("%lld")
// 64 位输出请用 printf("%lld")
当提交成功后，会展示如下界面，那么恭喜这道题目就通过了！
小结
祝愿所有的伙伴都能拿到自己心仪的Offer！📣伙伴们点击右边链接立刻开启刷题吧：牛客——刷题网
文章出处登录后可见！
