初探動態規劃（三）

State Transfer Equations!

State Transfer Equations!

State Transfer Equations!

動態規划出到第三篇，其實大家也應該發現了一個常識。狀態轉移方程的目的就是為了簡化運算，通過N步迭代，以空間換時間，得出結論。如果發現定義了狀態後，狀態轉移方程的表達依然非常複雜，需要經過大量複雜的運算，那麼也許是切入問題的角度不好，抑或是沒有正確定義狀態轉移方程。此時要麼重新定義狀態，或者重新定義方程。

今天以三題為例，觀察如何定義狀態與狀態轉移方程。

問題 一

給定一個二維0/1矩陣，找到並返回其中由1組成的最大正方形面積。

例一

1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0

該矩陣最大正方形面積是4

函數原型

int maximalSquare(vector<vector<char>>& matrix);

解析

此題首先需要分析如何組成正方形。假設我們定義，我們分析正方形最大面積的掃描形式，是從下往上，從右往左的。也就是說，我們看不到對於點 ，其右側和下側的情形。那麼我們只能從其上、左側分析。那麼基於這種方法，我們可以得知在例一的情況下，點 所能組成的最大正方形面積是1。而對於點 所能組成的最大正方形面積是4.

我們來分析一下 是如何得出面積為4的。以 為例，我們觀察其上方，左方，以及左上方，即點 的位置上，其字元是1。因此我們知道， 可以圍成一個更大的正方形。

那麼，我們定義一個二維數組 ,代表 點所能形成最大正方形的邊長。那麼根據以上的分析，我們如何得出狀態轉移方程呢？

若 能夠形成更大的正方形，有兩個條件：

• （首先他本身不能是0)
• （其次他上，左，左上不能是0)

那如果他上、左、左上區域就能圍成比較大的正方形呢？這就是我們定義 的目的所在。根據我們定義 的含義，我們列出狀態轉移方程

我們把這段單獨拿出來

該狀態轉移方程想要表達的是，計算 處最大正方形的邊長，他應該取 上、左、左上三處所能形成的最大正方形邊長中 最小的那一個，然後加1. 這種表示非常直觀，因為我們需要構成正方形，因此我們必須考慮滿足所有條件下的邊長，緊接著，因為自身不為0，因此最大正方形的邊長可以進行一次擴展。

至於此題的基線情況，則比較簡潔，構建方程如下

參考代碼

問題 二

尋找第n個丑數。

p.s. 丑數：該數的質因數只能由2,3,5組成。 其中1也是丑數（特例）。因此，前10個丑數是

例一

1012

第10個丑數是12.

函數原型

int nthUglyNumber(int n);

解析

此題相對比較好推。因為丑數是由質因數2,3,5組成的數，下一個丑數應該是在之前所有丑數中，某一個或者乘以2，,或者乘以3，或者乘以5，得到的恰比當前丑數大的最小的丑數，因此通過基線數,即1的前提下，不斷往下推即可。

定義 代表第 個丑數。那麼狀態轉移方程是

同時，若 中的某一個,則對應下標 自增。

參考代碼

問題 三

給定一個字元串，返回該字元串中一共有多少個迴文子串。

注意，即使子串內容相同，但是子串在原字元串中的開始位置或結束位置不同，算作不同的子串。

例一

輸入: "abc"輸出: 3"abc"中一共有三個迴文子串: "a","b","c".

例二

輸入:"aaa"輸出:6"aaa"中一共有六個迴文子串:"a","a","a","aa","aa","aaa".

函數原型

int countSubstrings(string s);

解析

直接定義狀態和狀態轉移方程

假設二維數組 代表從 下標 開始到 下標 結束擁有迴文子串的數量。

那麼狀態轉移方程是

這個狀態轉移方程表示的是，對於 擁有的迴文數量，首先看 以及 的迴文數量，同時需要注意的是 無論是 還是 ，他們都包含了 擁有的迴文數量，因此也就是 我們計算了兩次，需要減去一次。同時，我們還需要考慮 字元串子串是否能夠構成迴文。因為在狀態轉移方程中，我們考慮的是 的迴文數量。

基線情況:

,

參考代碼