動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù))

動(dòng)態(tài)規(guī)劃法求最長(zhǎng)非連續(xù)增序子序列

問(wèn)題描述

一個(gè)整形數(shù)組a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1為一個(gè)遞增子序列長(zhǎng)度為2， a0 a2 a5 a6為一個(gè)遞增序列，其長(zhǎng)度為4，且為最長(zhǎng)的遞增子序列。

解決方案

設(shè)b[j]為以a[j]結(jié)束的最長(zhǎng)遞增序列的長(zhǎng)度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。問(wèn)題的答案為max(b[j]) 1<= j <= n 。

解決方法類(lèi)似求最大連續(xù)子序列和的問(wèn)題。

代碼如下

定義s[i] 表示第i個(gè)位置處，以a[i]為結(jié)尾的最大遞增長(zhǎng)度

先求每個(gè)位置處的最大長(zhǎng)度，然后遍歷求最大長(zhǎng)度即可

下面一步增加一個(gè)存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)究竟是哪幾個(gè)數(shù)組構(gòu)成了遞增的最大長(zhǎng)度的數(shù)組

#include <iostream>

using namespace std ;

const int N = 1010 ;

int s[N] ;

int a[N] ;

int p[N] ; //p[i] 表示以a[i]結(jié)尾的最長(zhǎng)子串的前一個(gè)節(jié)點(diǎn)的標(biāo)號(hào)

int main()

{

int n , i , k;

scanf("%d" , &n) ;

for(i = 0 ; i < n ;i++)

{

scanf("%d" ,&a[i]);

s[i] = 1 ;

p[i] = i ; //初始化每一個(gè)路徑

}

for(i = 0 ; i < n ; i++)

{

for(k = 0 ; k < i ; k++)

{

if(a[i] > a[k])

{

int q = s[k] + 1 ;

if(s[i] < q)

{

s[i] = q ;

p[i] = k ;

}

int max = 0 ;

for(i = 0 ; i < n ;i++)

{

if(s[max] < s[i])

max = i ;

}

printf("%d\n" , s[max]) ;

while(1)

{

printf("%d->" , a[max]) ;

if(max == 0)

break ;

max = p[max] ;

}

system("pause");

return 0 ;

}

posted on 2011-04-21 14:11 kahn 閱讀(1908) 評(píng)論(3) 編輯收藏引用

Feedback

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-10 17:14 wangyan

讀師兄博客受益匪淺。。
PS：我覺(jué)得if(max == 0)
打印的時(shí)候應(yīng)當(dāng)改為if（max==P[max]）
不然的話，若增序列不是從第一個(gè)開(kāi)始，比如100 1 2 3 4，就會(huì)死循環(huán)。回復(fù) 更多評(píng)論

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-20 17:46 杜明

@wangyan
我的垃圾博客就怕誤人子弟，我都是很隨意的寫(xiě)的。
http://blog.csdn.net/v_JULY_v/
這個(gè)網(wǎng)址是csdn上一個(gè)大牛寫(xiě)的，非常好。各種算法還有分析。推薦你看看。回復(fù) 更多評(píng)論

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-20 17:47 杜明

我的垃圾博客就怕誤人子弟，我都是很隨意的寫(xiě)的。
http://blog.csdn.net/v_JULY_v/
這個(gè)網(wǎng)址是csdn上一個(gè)大牛寫(xiě)的，非常好。各種算法還有分析。推薦你看看。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類(lèi)

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù))

動(dòng)態(tài)規(guī)劃法求最長(zhǎng)非連續(xù)增序子序列

問(wèn)題描述

一個(gè)整形數(shù)組a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1為一個(gè)遞增子序列長(zhǎng)度為2， a0 a2 a5 a6為一個(gè)遞增序列，其長(zhǎng)度為4，且為最長(zhǎng)的遞增子序列。

解決方案

設(shè)b[j]為以a[j]結(jié)束的最長(zhǎng)遞增序列的長(zhǎng)度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。問(wèn)題的答案為max(b[j]) 1<= j <= n 。

解決方法類(lèi)似求最大連續(xù)子序列和的問(wèn)題。

代碼如下

Feedback

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-10 17:14 wangyan

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-20 17:46 杜明

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-20 17:47 杜明

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類(lèi)

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù))

動(dòng)態(tài)規(guī)劃法 求最長(zhǎng)非連續(xù)增序子序列

問(wèn)題描述

一個(gè)整形數(shù)組a[]= {1 ,7, 3, 5, 9, 4, 8}，其中a0 ，a1為一個(gè)遞增子序列長(zhǎng)度為2， a0 a2 a5 a6為一個(gè)遞增序列，其長(zhǎng)度為4，且為最長(zhǎng)的遞增子序列。

解決方案

設(shè)b[j]為以a[j]結(jié)束的最長(zhǎng)遞增序列的長(zhǎng)度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。 問(wèn)題的答案為max(b[j]) 1<= j <= n 。

解決方法類(lèi)似求最大連續(xù)子序列和的問(wèn)題。

代碼如下

Feedback

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-10 17:14 wangyan

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-20 17:46 杜明

# re: 動(dòng)態(tài)規(guī)劃法-----最長(zhǎng)增序子序列(非連續(xù)) 2011-08-20 17:47 杜明

動(dòng)態(tài)規(guī)劃法求最長(zhǎng)非連續(xù)增序子序列

設(shè)b[j]為以a[j]結(jié)束的最長(zhǎng)遞增序列的長(zhǎng)度，則b[j] = max(b[k]) ，其中1<=k<j ,且a[k] < a[j] 。問(wèn)題的答案為max(b[j]) 1<= j <= n 。