??個(gè)人主頁(yè)：一二三o-0-O的博客
??技術(shù)方向：C/C++客戶端資深工程師（直播+音視頻剪輯）
?????作者簡(jiǎn)介：數(shù)據(jù)結(jié)構(gòu)算法與音視頻領(lǐng)域創(chuàng)作者
?? 系列專欄：?？途W(wǎng)面試必刷
??專欄目標(biāo)：幫助伙伴們通過(guò)系統(tǒng)訓(xùn)練，掌握數(shù)據(jù)結(jié)構(gòu)與算法，收獲心儀Offer
??推薦一個(gè)找工作神器：?？退㈩}網(wǎng) 【面試經(jīng)驗(yàn)|實(shí)習(xí)招聘內(nèi)推，求職就業(yè)一戰(zhàn)解決】
??如果對(duì)您有幫助的話，歡迎點(diǎn)贊??收藏??，關(guān)注不迷路
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧篇系列文章：
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（一）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（二）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（三）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（四）
【算法入門(mén)必刷】數(shù)據(jù)結(jié)構(gòu)-棧（五）
【算法入門(mén)必刷】動(dòng)態(tài)規(guī)劃-線性dp篇系列文章：
【算法面試入門(mén)必刷】動(dòng)態(tài)規(guī)劃-線性dp（一）
【算法面試入門(mén)必刷】動(dòng)態(tài)規(guī)劃-線性dp（二）
【算法面試入門(mén)必刷】動(dòng)態(tài)規(guī)劃-線性dp（三）
前言
開(kāi)啟刷題，請(qǐng)點(diǎn)擊右邊鏈接進(jìn)行跳轉(zhuǎn)點(diǎn)擊這里
算法入門(mén)刷題訓(xùn)練
題目AB37：最長(zhǎng)上升子序列(一)
題目分析
描述
給定一個(gè)長(zhǎng)度為 n 的數(shù)組 arr，求它的最長(zhǎng)嚴(yán)格上升子序列的長(zhǎng)度。
所謂子序列，指一個(gè)數(shù)組刪掉一些數(shù)（也可以不刪）之后，形成的新數(shù)組。例如 [1,5,3,7,3] 數(shù)組，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 則不是它的子序列。
我們定義一個(gè)序列是 嚴(yán)格上升 的，當(dāng)且僅當(dāng)該序列不存在兩個(gè)下標(biāo) i 和 j 滿足 i<j 且 arr i ≥ arr j.
這道題目與上一篇【算法面試入門(mén)必刷】動(dòng)態(tài)規(guī)劃-線性dp（三）中練習(xí)的連續(xù)子數(shù)組最大和有個(gè)不同就是，要求的子數(shù)組不是連續(xù)的。因此可以定義動(dòng)態(tài)規(guī)劃數(shù)組dp[i] 表示以第i個(gè)數(shù)字為結(jié)尾的最長(zhǎng)連續(xù)子序列的長(zhǎng)度。從而推導(dǎo)出遞推公式：dp[i] = maxLength + 1，其中maxLength表示從下標(biāo)0到i-1中dp數(shù)組最大值（最大的連續(xù)子序列的長(zhǎng)度）。
理論準(zhǔn)備
任何算法都有相對(duì)應(yīng)的算法模板或者有規(guī)律的解題步驟。對(duì)于動(dòng)態(tài)規(guī)劃來(lái)講，做DP相關(guān)的算法題要熟練掌握下面DP解題步驟，這樣有助于在面對(duì)到各種各樣的題目時(shí)能夠提高解題效率：
DP解題步驟:
- 首先要確定dp數(shù)組：是一維，二維還是三維；以及下標(biāo)的含義是什么？
- 根據(jù)確定好的dp數(shù)組，給出遞推公式，也叫狀態(tài)轉(zhuǎn)移方程。
- 確定dp數(shù)組是否需要初始化，初始化為多少。
- 確定遍歷的順序；這一步在背包相關(guān)的DP題目中非常重要。
- 根據(jù)測(cè)試用例進(jìn)行驗(yàn)證
題解
具體的解決方案如下：
- 首先確定dp數(shù)組：是一維，二維還是三維；以及下標(biāo)的含義是什么？
// 這里使用一維dp
// dp[i] 表示以第i個(gè)數(shù)字為結(jié)尾的最長(zhǎng)連續(xù)子序列的長(zhǎng)度
vector<int> dp(n);
- 根據(jù)確定好的dp數(shù)組，給出遞推公式。
// 根據(jù)題目分析得出了以下遞推公式：
// dp[i] = maxLength + 1，其中maxLength表示從下標(biāo)0到i-1中dp數(shù)組最大值（當(dāng)前值之前的最大的連續(xù)子序列的長(zhǎng)度）。
int maxValue{};
// 求得從下標(biāo)0到下標(biāo)i-1中dp值的最大值
for(int j{};j<i;++j){
// 當(dāng)當(dāng)前值大于v[j]，才進(jìn)行dp[j]的判斷
if(v[i] > v[j]){
maxValue = max(maxValue,dp[j]);
}
}
// 然后dp[i]就等于之前的最大的連續(xù)子序列的長(zhǎng)度加上當(dāng)前數(shù)值
dp[i] = maxValue + 1;
- 確定dp數(shù)組是否需要初始化，初始化為多少。
// 根據(jù)dp[i]的定義，子序列的最短長(zhǎng)度都是本身即1
vector<int> dp(n,1);
- 確定遍歷的順序；這一步在背包相關(guān)的DP題目中非常重要。
// 本題從小到大遍歷i
for(int i{1};i<n;++i){
int maxValue{};
// 內(nèi)部從小到大，從大到小都可以
for(int j{};j<i;++j){
if(v[i] > v[j]){
maxValue = max(maxValue,dp[j]);
}
}
}
-
根據(jù)測(cè)試用例進(jìn)行驗(yàn)證：選擇所有的測(cè)試用例帶入驗(yàn)證即可。
-
完整代碼如下：
#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個(gè)數(shù)字為結(jié)尾的最長(zhǎng)連續(xù)子序列的長(zhǎng)度
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 位輸出請(qǐng)用 printf("%lld")
// 64 位輸出請(qǐng)用 printf("%lld")
當(dāng)提交成功后，會(huì)展示如下界面，那么恭喜這道題目就通過(guò)了！
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-781077.html
小結(jié)
祝愿所有的伙伴都能拿到自己心儀的Offer！??伙伴們點(diǎn)擊右邊鏈接立刻開(kāi)啟刷題吧：?？汀㈩}網(wǎng)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-781077.html
到了這里，關(guān)于猿創(chuàng)征文 |【算法面試入門(mén)必刷】動(dòng)態(tài)規(guī)劃-線性dp（四）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
