狀態設計優化

概述

優化 dp 時，不止可以從轉移過程入手，加速轉移。有時，也可以從狀態定義入手，通過改變設計狀態的方式實現複雜度上的優化。

令人比較頭疼的是，這類優化大多不具有通用性，即不能很套路地應用於多個題目中。因此，下文將從具體例題出發，力求提供思路上的啓發，希望可以對讀者有一定幫助。

題面

給定兩個長度分別為 \(n,m\) 且僅由小寫字母構成的字符串 \(A,B\), 求 \(A,B\) 的最長公共子序列。\((n\le 10^6,m\le 10^3)\)

您一眼秒了它，這不是板子嗎？

定義狀態 \(f_{i,j}\) 為 \(A\) 的前 \(i\) 位與 \(B\) 的前 \(j\) 位最長公共子序列，則有

\[ f_{i,j}= \begin{cases} \max(f_{i-1,j},f_{i,j-1}) & ,A_i \neq B_j \\ f_{i-1,j-1}+1 & ,A_i = B_j \end{cases} \]

上述做法的時間複雜度 \(O(nm)\)，無法通過本題。

我們仔細一想，發現了一個性質：最終答案不會超過 \(m\)。

我們又仔細一想，發現 LCS 滿足貪心的性質。

更改狀態定義 \(f_{i,j}\) 為與 \(B\) 前 \(i\) 位的最長公共子序列長度為 \(j\) 的 \(A\) 的最短前綴長度（即將樸素做法的答案與第一維狀態對調）

可以通過預處理 \(A\) 的每一位的下一個 \(a,b,\cdots,z\) 的出現位置進行 \(O(1)\) 的順推轉移。

複雜度 \(O(m^2+26n)\)，可以通過本題。

題面

給定一個 \(n\) 個點的無權有向圖，判斷該圖是否存在哈密頓迴路。\((2\le n\le 20)\)

看到數據範圍，我們考慮狀壓。

設 \(f_{s,i}\) 表示從點 \(1\) 出發，僅經過點集 \(s\) 中的點能否到達點 \(i\)。記 \(g\) 為原圖的鄰接矩陣。則有

\[ f_{s, i} = \bigvee_{j\in s, j\neq i}f_{s \setminus \{i\}, j}\wedge g_{j, i} \left(i\in s\right) \]

時間複雜度 \(O(n^2 \times 2^n)\)，寫得好看或許能過，但是並不優美。

上面的狀態設計中，每個 \(dp\) 值只代表一個 bool 值，這讓我們覺得有些浪費。

我們可以考慮對於每個狀態 \(s\) 將 \(f_{s,1},f_{s,2},\dots,f_{s,n}\) 壓成一個 int，發現我們可以將鄰接矩陣同樣壓縮後進行 \(O(1)\) 轉移。

時間複雜度 \(O(n^2/w\times 2^n)\), 可以通過這道題，其中 \(w\) 為 int 的位數。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Marcythm, partychicken, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用