這個是用動態規劃做的一道題，先學習一下動態規劃的概念吧。?? 用動態規劃解題，就是要把問題分解為一個個子問題，對子問題進行求解，而子問題又可以繼續進行分解，直到一定小的規模。 DP與遞歸類似，但遞歸會導致重復計算，而用DP每次計算后的子問題的解都會被保存起來，從而避免了重復計算，保證了效率，比如本題用maxlen[]保存每個狀態值 對于每組與子問題有關系的變量，我們對他們進行取值，稱之為子問題的“狀態”，而“狀態”的值就是該子問題的解。 定義出什么是“狀態”、得到“狀態”的值后，就要找出不同狀態之間的遷移關系，即通過一個狀態求另一個狀態的值，往往有一個遞推公式，我們把這個遞推公式成為狀態轉移方程。 現在反過來看這道題：
輸入數據
輸入的第一行是序列的長度N (1 <= N <= 1000)。第二行給出序列中的 N 個整數，這些
整數的取值范圍都在0 到10000。
輸出要求
最長上升子序列的長度。
輸入樣例
7
1 7 3 5 9 4 8
輸出樣例
4 問題分析： 怎么分解成子問題呢？我們把“以a_k為終點的序列的最長上升子序列的長度”作為問題的子問題，其中k = 1,2,3......N . 這樣就把問題分解為N個子問題，只要我們把這N個子問題解決了，從中找出解值最大的即為原問題的解 怎么求狀態轉移方程呢？顯然當k = 1的時候，maxlen[k] = 1;而通過k=1這個狀態求別的狀態的轉移方程則可以寫成： maxlen[k] = (max(maxlen[i])，i = 1,2,3,....,k-1&& str[i] < str[k]) + 1; 這個方程的含義是：要求以a_k為終點的序列的最長上升子序列的長度，只要算出以滿足條件的a_k左邊的某一個數為終點的序列的最長上升子序列的長度 再 加上a_k這個數，即長度再加1即可，得到的這樣一個序列必定是包含a_k的 這里要充分理解遞歸的思想（雖然這里并不用到遞歸函數） 1 #include <iostream> 2 using namespace std; 3 4 int str[1001]; 5 int maxlen[1001]; 6 int p[1001]; 7 8 int main() 9 { 10 int N;cin >> N; 11 memset(str,0,sizeof(str)); 12 for(int i = 1;i < N;i++) 13 cin >> str[i]; 14 memset(maxlen,0,sizeof(maxlen)); 15 maxlen[1] = 1; 16 for(int i = 2;i < N ;i++){ 17 int temp = 0; 18 for(int j = 1;j < i;j++){ 19 if(str[j] < str[i]) 20 if(temp < maxlen[j]) 21 temp = maxlen[j]; 22 } 23 maxlen[i] = temp + 1; 24 } 25 int temp = -1; 26 for(int i = 1;i < N ;i++){ 27 if(temp < maxlen[i]) 28 temp = maxlen[i]; 29 } 30 cout << temp; 31 }

?

轉載于:https://www.cnblogs.com/amghost/archive/2012/06/06/2537520.html

總結

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

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