學(xué)習(xí)交流加

• 個(gè)人qq：
  1126137994
• 個(gè)人微信：
  liu1126137994
• 學(xué)習(xí)交流資源分享qq群：
  962535112

這是一個(gè)經(jīng)典的LIS(即最長(zhǎng)上升子序列)問(wèn)題，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡量?jī)?yōu)的解法求出序列的最長(zhǎng)上升子序列的長(zhǎng)度。

給定一個(gè)序列arr及它的長(zhǎng)度n(長(zhǎng)度小于等于500)，請(qǐng)返回LIS的長(zhǎng)度。

測(cè)試樣例：
[2,1,5,3,6,4,8,9,7],9
返回：5

分析思路：化簡(jiǎn)到子問(wèn)題，那么這道題應(yīng)該是化簡(jiǎn)到求該序列長(zhǎng)度的前1,2,3,4,5,6…n個(gè)數(shù)的最長(zhǎng)上升子序列問(wèn)題

那么同樣是開(kāi)辟一個(gè)數(shù)組dp[n] 這里開(kāi)辟的是數(shù)組還是矩陣，是根據(jù)實(shí)際情況而來(lái)。那么dp[i]就代表必須以arr[i]結(jié)尾的情況下，arr[0…i]的最長(zhǎng)上升子序列的長(zhǎng)度。

由上圖的分析可知：
dp[0]=1;
dp[1] 取決于arr[1]是否大于arr[0] 本題是不大于，所以dp[1]=1;
dp[2]取決于arr[2]是否大于arr[j]（j=0~1），大于arr[j]的話，那么就取dp[j]+1的最大值
dp[3]取決于arr[3]是否大于arr[j]（j=0~2），大于arr[j]的話，那么就取dp[j]+1的最大值
dp[4]取決于arr[4]是否大于arr[j]（j=0~3），大于arr[j]的話，那么就取dp[j]+1的最大值

那么dp[i]的表達(dá)式就應(yīng)該是：
dp[i]=max{dp[j]+1(j=0~(i-1)),且arr[i]>arr[j]}

由以上分析，可寫(xiě)程序如下：

class LongestIncreasingSubsequence { public:int getLIS(vector<int> A, int n) {// write code hereint dp[n];/* 初始化dp */for(int i=0;i<n;i++){dp[i]=1;}int Max=1;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(A[i]>A[j]){//注意dp[j]+1這個(gè)表達(dá)式只能放到判斷語(yǔ)句里面，這樣才不會(huì)改變它的值（只做判斷），//如果改變了dp[j]的值，將會(huì)影響下一次循環(huán)的計(jì)算if((dp[j]+1)>dp[i]) dp[i]=dp[j]+1;}}/* 外部每循環(huán)一次，則求得了dp[i]的值，選出每次循環(huán)后得到的最大值，就是最終需要返回的值 */if(dp[i]>Max)Max=dp[i];;}return Max;} };

動(dòng)態(tài)規(guī)劃的思想！！！化整體為0,1,2…先計(jì)算子問(wèn)題，再合并計(jì)算整體問(wèn)題！！！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【常见笔试面试算法题12续集三】动态规划算法案例分析3 LIS练习题（最长上升子序列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。