【Tai_mount】 算法學習 - 線性動态規劃 - 子序列問題的DP意義

VeritasDaLao教了我這東西一整個下午+半個早上，終于學會樂。

做完飛彈攔截/最長公共子序列以後我問Veritas：為什麼我不覺得這是DP，而它們出現在luogu的“線性動态規劃”題單中。

原來是我跳了N^2直接看到第一個題解……是以沒經過DP的那個思路。

他還給我推薦了一篇部落格：​​https://www.luogu.com.cn/blog/pks-LOVING/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie​​

LIS問題

LIS問題就是最長上升（不下降）子序列問題，也可同樣推廣至“下降/不上升”。

給定seq[]長度為n的序列，要求輸出LIS（最長上升子序列）的長度。

有兩種做法如下：

做法一

dp[i]：seq[1~i]的LIS長度。

轉移方程：dp[i]=max{dp[k]+1} (k<i&&a[k]<a[i])

這個想法很自然，外層循環i=1n，内層循環k=1i-1,if(a[k]<a[i]) dp[i]=max(a[k]+1,dp[i])

注意一點，初始指派應為dp[1~i]=1，無論如何dp[i]最小都為1

dp[n]即為最後答案。

現在的算法是O(N)*O(N)，通過樹狀數組/線段樹可以把内層優化成logn。

寫這篇博文的時候有段時間沒複習過線段樹了。（我的線段樹也是Veritas教的呢太感謝他啦）是以先省略這部分。

之前記筆記在有道雲記的，一會兒再把線段樹的筆記發上來。

做法二

就是這個做法讓我想了一下午加半上午

dp[i][j]：該序列前j個數，長度為i的LIS序列的末尾元素的最小值

轉移方程：

dp[i][j]=min{dp[i][j],a[j]} (dp[i-1][j-1]<a[j])

dp[i][j]=min{dp[i][j],dp[i][j-1]}

dp數組均賦初值為INF(無窮大)

我們所求為 max{i}(dp[i][n]!=INF)，這和題目意義是一樣的。dp[][]=INF意味着沒更新到，就是不存在那個子序列。我們要找的就是有意義的，最長的子序列

我們來畫一張圖：

紅格子是我們想要更新的格子，就是那個dp[i][j]（此處i=j隻是特例，标上數字隻是為了更形象化）

它首先一定可以由dp[i][j-1]，即橙色格子轉移而來（讨論的前提是dp[i][1]能被更新到哈~），這樣紅格子初值為INF，橙必比紅小，通過dp[i][j]=min{dp[i][j],dp[i][j-1]}，就使得橙，紅一樣了。

而後考慮，可以由黃更新而來，前提是綠<黃。

（感覺上面有點說廢話）

黃那一列都是已知條件，是以紅隻需要我們先推出來綠，橙就可以了，其他白格子都是不需要的，可以被覆寫（類似01背包），綠和橙的j相等，在同一行裡，這意味着我們可以把表格縮成一行，變成一維的，dp[i]。

這意味着我們不能在紅之前更新紅左邊的白，因為這會把綠覆寫過去，是以我們必須外層j循環内層i循環且i倒序。

……我這個地方蒙了好久，莫名，以後記住隻要畫張圖就清楚了。

縮成一維以後就是這樣：

同一個j1，可能會更新若幹個dp[i]。如果它更新了若幹個dp[x1]……dp[xn],且xn>……>x1。此時dp[x1……xn]=a[j1],對于x1……xn,後面一定是要一起更新x1+1,x2+1……xn+1的，要不大家都不能更新，要不然都更新。因為他們的dp[x]值都一樣，我們更新時的判斷就是隻看dp[x]的值。

如果大家都不更新，自然大家都沒用可以丢了，如果大家都更新了，我們發現xn更新出來的xn+1>x(n-1)+1>……>x1+1。誰可能會是答案呢？隻有可能是xn+1，我們要取的是下标的最大值啊……那怎麼更新後面綴着的x1……x(n-1)都不可能把答案更新出來，是以他們就可以去死了。或者說，我壓根就不想生出來他們。

我是倒序枚舉的i，遇到的第一個滿足條件的然後break就好。後面的不用管，沒用。

内層循環我們可以了解為：我們其實在求dp[]這個序列裡從右往左數的第一個小于a[j]的。

接下來是另一個性質：

首先剛開始dp[]是單增的（全是INF），若某次a[j]更新了dp[i]，就說明a[j]>dp[i-1]，此時dp[i]被更新，更新出來最小也是a[j]。是以dp[i]>dp[i-1]。

單增的序列，求從右數第一個小于a[j]的數，然後把它後面第一個數換掉……這樣就可以二分logn的複雜度了……呵呵呵呵呵呵，這不是從左數第一個大于等于a[j]的數換掉嘛……外層循環還是從1~n，是以我們發現：

和上一篇博文的程式一樣了！

但我們知道為什麼它是一個動歸了。。

神奇！！！！