正文內容

提高篇——動態規劃專題-資料下載頁

2026-07-27 06:31本頁面

　　

【正文】序上升子序列，像 (1, 7)， (3, 4, 8)和許多其他的子序列。在所有的子序列中，最長的上升子序列的長度是 4，如 (1, 3, 5, 8)。 ? 現在你要寫一個程序，從給出的數列中找到它的最長上升子序列。 ? 輸入 ? 輸入包含兩行，第一行只有一個整數 N（ 1 = N = 1000），表示數列的長度。 ? 第二行有 N個自然數 ai， 0 = ai = 10000，兩個數之間用空格隔開。 ? 輸出 ? 輸出只有一行，包含一個整數，表示最長上升子序列的長度。 ? 樣例輸入 ? 7 ? 1 7 3 5 9 4 8 樣例輸出 4 最長公共子序列（ LCS） ? 給定兩個字符串（或數字序列） A和 B，求一個字符串，使得這個字符串是 A和 B的最長公共部分（子序列可以不連續）。 ? 樣例： ? 如樣例所示，字符串“ sadstory”與“ adminsorry”的最長公共子序列為“ adsory”，長度為 6。 ? 令 dp[i][j]表示字符串 A的 i號位和字符串 B的 j號位之前的 LCS長度（下標從 1開始），如 dp[4][5]表示“ sads”與“ admin”的 LCS長度。那么可以根據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號位和字符串 B的 j號位之前的 LCS無法延長，因此 dp[i][j]將會繼承dp[i1][j]與 dp[i][j1]中的較大值，即有dp[i][j]=max{dp[ia][j]， dp[i][j1]}。狀態轉移方程：邊界： dp[i][0]=dp[0][j]=0(0=i=n,0=i=m) 時間復雜度： O(nm) 輸入數據： sadstory adminsorry 輸出結果： 6 最長回文子串給出一個字符串 S，求 S的最長回文子串的長度。樣例：字符串“ PATZJUJZTACCBCC”的最長回文子串為“ ATZJUJZTA”，長度為 9。最長回文子串是否能轉換為最長公共子序列（ LCS）來求解？把字符串 S倒過來變成字符串 T，然后對 S和 T進行LCS模型求解，得到的結果就是需要的答案。一旦 S中同時存在一個子串和它的倒序，那么答案就會出錯。例如字符串 S=“ABCDZJUDCBA”，將其倒過來之后變成T=“ABCDUJZDCBA”，這樣得到最長公共子串為 ”ABCD”，長度為 4，事實上 S的最長回文子串長度為 1。 ? 令 dp[i][j]表示 S[i]至 S[j]所表示的子串是否是回文子串，是則為 1，不是為 0。這樣根據 S[i]是否等于 S[j]，可以把轉移情況分為兩類：（ 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]一定不是回文子串。狀態轉移方程：邊界： dp[i][j]=1,dp[i][i+1]=(S[i]==S[i+1])?1:0 時間復雜度： O(n2) 存在問題：如果按照 i和 j從小到大的順序來枚舉子串的兩個端點，然后更新 dp[i][j]，會無法保證 dp[i+1][j1]已經被計算過，從而無法得到正確的 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]，初始化未得到因此無法狀態轉移！！！怎么辦？ …… …… …… 尋找新的枚舉方式 ? 根據遞推寫法，邊界表示的是長度為 1和 2的子串，且每次轉移都對子串的長度減了 1，因此第一遍將長度為 3的子串的 dp值全部求出，第二遍求出長度為 4的子串的 dp值 ……這樣就可以避免狀態無法轉移的問題。 ? 其他做法： ? 二分 +字符串 hash，復雜度 O(nlogn)。 ? Manacher算法，復雜度 O(n)。

點擊復制文檔內容

法律信息相關推薦

鄂ICP備17016276號-1

^{<blockquote id="jri91"></blockquote>}

提高篇——動態規劃專題-資料下載頁

工學動態規劃ppt課件-資料下載頁

動態規劃ppt課件(2)-資料下載頁

動態規劃網絡ppt課件-資料下載頁

優化模型動態規劃ppt課件-資料下載頁

動態規劃應用舉例ppt課件-資料下載頁

noip教程動態規劃ppt課件-資料下載頁

資源背包動態規劃ppt課件-資料下載頁

動態規劃背包問題ppt課件-資料下載頁

noip動態規劃講解ppt課件-資料下載頁

區間類型動態規劃ppt課件-資料下載頁

遞歸、分治、動態規劃、回溯-資料下載頁

動態規劃資源分配問題-資料下載頁

動態規劃理論部分ppt課件-資料下載頁

動態規劃模型舉例ppt課件-資料下載頁

ascal動態規劃普及組-資料下載頁

提高篇——動態規劃專題(存儲版)

提高篇——動態規劃專題-文庫吧在線文庫

提高篇——動態規劃專題(完整版)

提高篇——動態規劃專題(更新版)

提高篇——動態規劃專題(專業版)