問題：一個序列有N個數：A[1],A[2],…,A[N]，求出最長非降子序列的長度

樣例輸入：3 1 2 6 5 4

思路：?首先把問題簡單化。可以先求A[1],...A[i]的最長非降子序列，令dp[i]為以A[i]結尾的最長非降子序列。當i?= 1?時，?明顯是長度dp[1]?= 1?； i = 2?時，前面沒有比1小的數字，故dp[2]=1?，?此時的最長非降子序列為1?; i = 3?時,比數字2小的數是1?，并且只有1?，?分析可知?dp[3] = dp[2]+1；當i?= 4?時，找到比數字6小的數有 3 1 2?，求最長子序列，就應該找到前面的最長子序列的最大值?max{ dp[1],dp[2],dp[3]?},此時dp[4]=max{dp[j]+1}?,(j<4 , A[j]<A[4]) ;通過分析，我們可以歸納出狀態轉移方程為?dp[i] = max{dp[j]+1 , 1}(j<i , A[j]<A[i]) ; ?

下面是代碼：

/* 最長非降子序列 2015年8月26日10:19:00 動態規劃 */#include<iostream>using namespace std ;int LIS (int A[] , int n );int main (){int A[] = {3,1,2,6,4,5} ;cout << LIS (A,6);return 0;}int LIS (int A[] , int n ){int *dp = new int[n] ;dp[0] = 0 ;int len = 1;int i , j ;for ( i=1 ; i < n ; i ++ ){dp[i] = 1 ;for ( j = 0 ; j <i ; j ++){if (A[j]<A[i]&&dp[j]+1>dp[i])dp[i] = dp[j]+1 ;if ( len < dp[i] )len = dp [i] ;}}delete []dp ;return len ; }
僅作個人理解，希望對沒有基礎的人有幫助

總結

以上是生活随笔為你收集整理的动态规划 - 最长递增子序列LIS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。