提高篇——?jiǎng)討B(tài)規(guī)劃專題-資料下載頁
2025-08-05 06:31本頁面
【正文】 序上升子序列，像 (1, 7)， (3, 4, 8)和許多其他的子序列。在所有的子序列中，最長的上升子序列的長度是 4，如 (1, 3, 5, 8)。 ? 現(xiàn)在你要寫一個(gè)程序，從給出的數(shù)列中找到它的最長上升子序列。 ? 輸入 ? 輸入包含兩行，第一行只有一個(gè)整數(shù) N（ 1 = N = 1000），表示數(shù)列的長度。 ? 第二行有 N個(gè)自然數(shù) ai， 0 = ai = 10000，兩個(gè)數(shù)之間用空格隔開。 ? 輸出 ? 輸出只有一行，包含一個(gè)整數(shù)，表示最長上升子序列的長度。 ? 樣例輸入 ? 7 ? 1 7 3 5 9 4 8 樣例輸出 4 最長公共子序列（ LCS） ? 給定兩個(gè)字符串（或數(shù)字序列） A和 B，求一個(gè)字符串，使得這個(gè)字符串是 A和 B的最長公共部分（子序列可以不連續(xù)）。 ? 樣例： ? 如樣例所示，字符串“ sadstory”與“ adminsorry”的最長公共子序列為“ adsory”，長度為 6。 ? 令 dp[i][j]表示字符串 A的 i號(hào)位和字符串 B的 j號(hào)位之前的 LCS長度（下標(biāo)從 1開始），如 dp[4][5]表示“ sads”與“ admin”的 LCS長度。那么可以根據(jù)A[i]和 B[j]的情況，分為兩種決策： （ 1）若 A[i]==B[j]，則字符串 A與字符串 B的 LCS增加了 1位，即有 dp[i][j]=dp[i1][j1]+1。 （ 2）若 A[i]!=B[j]，則字符串 A的 i號(hào)位和字符串 B的 j號(hào)位之前的 LCS無法延長，因此 dp[i][j]將會(huì)繼承dp[i1][j]與 dp[i][j1]中的較大值，即有dp[i][j]=max{dp[ia][j]， dp[i][j1]}。 狀態(tài)轉(zhuǎn)移方程： 邊界： dp[i][0]=dp[0][j]=0(0=i=n,0=i=m) 時(shí)間復(fù)雜度： O(nm) 輸入數(shù)據(jù)： sadstory adminsorry 輸出結(jié)果： 6 最長回文子串 給出一個(gè)字符串 S，求 S的最長回文子串的長度。 樣例： 字符串“ PATZJUJZTACCBCC”的最長回文子串為“ ATZJUJZTA”，長度為 9。 最長回文子串 是否能轉(zhuǎn)換為最長公共子序列（ LCS）來求解？ 把字符串 S倒過來變成字符串 T，然后對(duì) S和 T進(jìn)行LCS模型求解，得到的結(jié)果就是需要的答案。 一旦 S中同時(shí)存在一個(gè)子串和它的倒序，那么答案就會(huì)出錯(cuò)。 例如字符串 S=“ABCDZJUDCBA”，將其倒過來之后變成T=“ABCDUJZDCBA”，這樣得到最長公共子串為 ”ABCD”，長度為 4，事實(shí)上 S的最長回文子串長度為 1。 ? 令 dp[i][j]表示 S[i]至 S[j]所表示的子串是否是回文子串，是則為 1，不是為 0。這樣根據(jù) S[i]是否等于 S[j]，可以把轉(zhuǎn)移情況分為兩類： （ 1）若 S[i]==S[j]，那么只要 S[i+1]至 S[j1]是回文子串， S[i]至 S[j]就是回文子串；如果 S[i+1]至 S[j1]不是回文子串，則 S[i]至 S[j]也不是回文子串。 （ 2）若 S[i]!=S[j]，那么 S[i]至 S[j]一定不是回文子串。 狀態(tài)轉(zhuǎn)移方程： 邊界： dp[i][j]=1,dp[i][i+1]=(S[i]==S[i+1])?1:0 時(shí)間復(fù)雜度： O(n2) 存在問題：如果按照 i和 j從小到大的順序來枚舉子串的兩個(gè)端點(diǎn)，然后更新 dp[i][j]，會(huì)無法保證 dp[i+1][j1]已經(jīng)被計(jì)算過，從而無法得到正確的 dp[i][j]。 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 求解 dp[0][2]，即求解dp[1][1]，初始化得到 求解 dp[0][3]，即求解dp[1][2]，初始化得到 求解 dp[0][4]，即求解dp[1][3]，初始化 未 得到 因此無法狀態(tài)轉(zhuǎn)移?。?！怎么辦？ …… …… …… 尋找新的枚舉方式 ? 根據(jù)遞推寫法，邊界表示的是長度為 1和 2的子串，且每次轉(zhuǎn)移都對(duì)子串的長度減了 1，因此第一遍將長度為 3的子串的 dp值全部求出，第二遍求出長度為 4的子串的 dp值 ……這樣就可以避免狀態(tài)無法轉(zhuǎn)移的問題。 ? 其他做法： ? 二分 +字符串 hash，復(fù)雜度 O(nlogn)。 ? Manacher算法，復(fù)雜度 O(n)。
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1