今天聊一道 4 鍵鍵盤問題，這個問題挺有意思，而且可以明顯感受到：對 dp 數組的不同定義需要完全不同的邏輯，從而產生完全不同的解法。
首先看一下題目：
如何在 N 次敲擊按鈕后得到最多的 A？我們窮舉唄，對于每次按鍵，我們可以窮舉四種可能，很明顯就是一個動態規劃問題。
這種思路會很容易理解，但是效率并不高，我們直接走流程：對于動態規劃問題，首先要明白有哪些「狀態」，有哪些「選擇」。
具體到這個問題，對于每次敲擊按鍵，有哪些「選擇」是很明顯的：4 種，就是題目中提到的四個按鍵，分別是A、C-A、C-C、C-V（Ctrl簡寫為C）。
接下來，思考一下對于這個問題有哪些「狀態」？或者換句話說，我們需要知道什么信息，才能將原問題分解為規模更小的子問題？
你看我這樣定義三個狀態行不行：第一個狀態是剩余的按鍵次數，用n表示；第二個狀態是當前屏幕上字符 A 的數量，用a_num表示；第三個狀態是剪切板中字符 A 的數量，用copy表示。
如此定義「狀態」，就可以知道 base case：當剩余次數n為 0 時，a_num就是我們想要的答案。
結合剛才說的 4 種「選擇」，我們可以把這幾種選擇通過狀態轉移表示出來：
dp(n - 1, a_num + 1, copy), # A
解釋：按下 A 鍵，屏幕上加一個字符
同時消耗 1 個操作數
dp(n - 1, a_num + copy, copy), # C-V
解釋：按下 C-V 粘貼，剪切板中的字符加入屏幕
同時消耗 1 個操作數
dp(n - 2, a_num, a_num) # C-A C-C
解釋：全選和復制必然是聯合使用的，
剪切板中 A 的數量變為屏幕上 A 的數量
同時消耗 2 個操作數
這樣可以看到問題的規模n在不斷減小，肯定可以到達n = 0的 base case，所以這個思路是正確的：
PS：這個思路和前文 詳解一道騰訊面試題：編輯距離 有異曲同工之妙，如果有疑問的話可以去看看。
這個解法應該不難理解，因為語義明確。下面就繼續走流程，用備忘錄消除一下重疊子問題：
def maxA(N: int) -> int:
# 備忘錄
memo = dict()
def dp(n, a_num, copy):
if n <= 0: return a_num;
# 避免計算重疊子問題
if (n, a_num, copy) in memo:
return memo[(n, a_num, copy)]
memo[(n, a_num, copy)] = max(
# 幾種選擇還是一樣的
)
return memo[(n, a_num, copy)]
return dp(N, 0, 0)
這樣優化代碼之后，子問題雖然沒有重復了，但數目仍然很多，在 LeetCode 提交會超時的。
嘗試分析一下這個算法的時間復雜度，就會發現不容易分析。我們可以把這個 dp 函數寫成 dp 數組：
dp[n][a_num][copy]
# 狀態的總數（時空復雜度）就是這個三維數組的體積
我們知道變量n最多為N，但是a_num和copy最多為多少我們很難計算，復雜度起碼也有 O(N^3) 吧。所以這個算法并不好，復雜度太高，且已經無法優化了。
這也就說明，這樣定義「狀態」是不太優秀的，下面我們換一種定義 dp 的思路。
這種思路稍微有點復雜，但是效率高。繼續走流程，「選擇」還是那 4 個，但是這次我們只定義一個「狀態」，也就是剩余的敲擊次數n。
這個算法基于這樣一個事實，最優按鍵序列一定只有兩種情況：
要么一直按A：A,A,…A（當 N 比較小時）。
要么是這么一個形式：A,A,…C-A,C-C,C-V,C-V,…C-V（當 N 比較大時）。
因為字符數量少（N 比較小）時，C-A C-C C-V這一套操作的代價相對比較高，可能不如一個個按A；而當 N 比較大時，后期C-V的收獲肯定很大。這種情況下整個操作序列大致是：開頭連按幾個A，然后C-A C-C組合再接若干C-V，然后再C-A C-C接著若干C-V，循環下去。
換句話說，最后一次按鍵要么是A要么是C-V。明確了這一點，可以通過這兩種情況來設計算法：
int[] dp = new int[N + 1];
// 定義：dp[i] 表示 i 次操作后最多能顯示多少個 A
for (int i = 0; i <= N; i++)
dp[i] = max(
這次按 A 鍵，
這次按 C-V
)
對于「按A鍵」這種情況，就是狀態i - 1的屏幕上新增了一個 A 而已，很容易得到結果：
// 按 A 鍵，就比上次多一個 A 而已
dp[i] = dp[i - 1] + 1;
剛才說了，最優的操作序列一定是C-A C-C接著若干C-V，所以我們用一個變量j作為若干C-V的起點。那么j之前的 2 個操作就應該是C-A C-C了：
其中j變量減 2 是給C-A C-C留下操作數，看個圖就明白了：
這樣，此算法就完成了，時間復雜度 O(N^2)，空間復雜度 O(N)，這種解法應該是比較高效的了。
PS：這個思路跟前文 動態規劃設計之最長遞增子序列 有異曲同工之妙，如果有疑問可以去看看。
動態規劃難就難在尋找狀態轉移，不同的定義可以產生不同的狀態轉移邏輯，雖然最后都能得到正確的結果，但是效率可能有巨大的差異。
回顧第一種解法，重疊子問題已經消除了，但是效率還是低，到底低在哪里呢？抽象出遞歸框架：
def dp(n, a_num, copy):
dp(n - 1, a_num + 1, copy), # A
dp(n - 1, a_num + copy, copy), # C-V
dp(n - 2, a_num, a_num) # C-A C-C
看這個窮舉邏輯，是有可能出現這樣的操作序列C-A C-C，C-A C-C...或者C-V,C-V,...。顯然這種操作序列的結果不是最優的，但是我們并沒有想辦法規避這些情況的發生，從而增加了很多沒必要的子問題計算。
回顧第二種解法，我們稍加思考，發現最優的序列應該是這種形式：A,A..C-A,C-C,C-V,C-V..C-A,C-C,C-V..。
根據這個事實，我們重新定義了狀態，重新尋找了狀態轉移，從邏輯上減少了無效的子問題個數，從而提高了算法的效率。
