首先我們來看 LeetCode 第 343 題，其實(shí)動態(tài)規(guī)劃也包含了暴力求解，只不過我們按照一定規(guī)律，并且是在假設(shè)規(guī)模更小的問題已經(jīng)得到解決的情況下，得到了我們原先要解決的那個(gè)規(guī)模的問題的解，我個(gè)人認(rèn)為技巧在于“分類討論”，而“分類討論”的關(guān)鍵就在于“不重不漏”。
例題1：LeetCode 第 343 號問題：Integer Break
傳送門：343. 整數(shù)拆分。
給定一個(gè)正整數(shù) n，將其拆分為至少兩個(gè)正整數(shù)的和，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積。
示例 1:
輸入: 2 輸出: 1 解釋: 2 = 1 + 1, 1 × 1 = 1。示例 2:
輸入: 10 輸出: 36 解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。說明: 你可以假設(shè) n 不小于 2 且不大于 58。
說明：同《劍指 Offer》第 14 題：剪繩子。
思路1：回溯，也可以理解為“暴力搜索”。遍歷將一個(gè)數(shù)做分割的所有可能性，時(shí)間復(fù)雜度是 。
思路2：關(guān)鍵：“至少分割成兩個(gè)部分”。分析這個(gè)問題的遞歸結(jié)構(gòu)：“至少分割成兩個(gè)正整數(shù)” = “一個(gè)正整數(shù)” + “另一個(gè)還沒有分割的正整數(shù)”。這道題解題的關(guān)鍵在于“至少分割成兩個(gè)正整數(shù)”，從這個(gè)角度出發(fā)，就能夠得到我們“自頂向下”思考這個(gè)問題的路徑，進(jìn)而使用“記憶化搜索”或者“動態(tài)規(guī)劃”得到原問題的解。
畫出如下樹形結(jié)構(gòu)：
發(fā)現(xiàn)有大量重疊子問題。
定義狀態(tài)： 表示正整數(shù)
經(jīng)過分割以后得到的數(shù)字乘積的最大值。
則狀態(tài)轉(zhuǎn)移方程是：
從這個(gè)過程中體會：1、原問題的解是規(guī)模更小的子問題的解的組合；2、“狀態(tài)”定義好了，上面的那個(gè)等式，其實(shí)就是“狀態(tài)轉(zhuǎn)移方程”。
對于每一個(gè)狀態(tài)而言，還要再比較“不再繼續(xù)分割”和“繼續(xù)分割”，取當(dāng)中的最大值。由上面的思路，我們可以寫一個(gè)遞歸方法。
下面，我們給出 3 個(gè)解答，這 3 種方式的解答體現(xiàn)了我們思考“線性規(guī)劃”問題的一般步驟。
Java 代碼：不含記憶化搜索的遞歸
/**
* 沒有記憶化搜索的遞歸解法
* 這個(gè)版本提交給 LeetCode 是通不過的
* Created by liwei on 17/10/3.
*/
public class Solution {
public int integerBreak(int n) {
int res = breakInteger(n);
return res;
}
/**
* 將 n 進(jìn)行分割（至少分割成兩個(gè)部分），可以獲得乘積的最大值
* @param num
* @return 將 n 進(jìn)行分割得到的乘積最大值
*/
private int breakInteger(int num) {
if (num == 1) {
return 1;
}
int res = 0; // 這個(gè)初始值可以設(shè)置為 0 嗎，1 行不行？
for (int i = 1; i < num; i++) {
// 關(guān)鍵之處：狀態(tài)轉(zhuǎn)移方程，其中 i * (num - i) 這一步很關(guān)鍵，千萬不能漏掉
// 這里有一個(gè)陷阱，就是不能忽略能不能繼續(xù)分割的情況
res = max3(res, i * (num - i), i * breakInteger(num - i));
}
return res;
}
private int max3(int num1, int num2, int num3) {
int temp = Integer.max(num1, num2);
return Integer.max(temp, num3);
}
// 對于 2 和 3 這種分解之后乘積不超過自己的怎么辦？
public static void main(String[] args) {
Solution solution = new Solution();
int max = solution.integerBreak(3);
System.out.println(max);
}
}
Java 代碼：加入了記憶化搜索的遞歸
/**
* 加入了記憶化搜索的遞歸解法
* Created by liwei on 17/10/3.
*/
public class Solution2 {
private int[] memory;
public int integerBreak(int n) {
assert n >= 2;
memory = new int[n + 1];
memory[0] = 0;
memory[1] = 1;
for (int i = 2; i < n + 1; i++) {
memory[i] = -1;
}
int res = breakInteger(n);
return res;
}
// 將 n 進(jìn)行分割得到的乘積最大值
private int breakInteger(int num) {
if (num == 1) {
return 1;
}
if (memory[num] == -1) {
int res = 0; // 這個(gè)初始值可以設(shè)置為 0 嗎，1 行不行？
for (int i = 1; i < num; i++) {
// 關(guān)鍵之處：狀態(tài)轉(zhuǎn)移方程，其中 i * (num - i) 這一步很關(guān)鍵，千萬不能漏掉
res = max3(res, i * (num - i), i * breakInteger(num - i));
}
memory[num] = res;
}
return memory[num];
}
private int max3(int num1, int num2, int num3) {
int temp = Integer.max(num1, num2);
return Integer.max(temp, num3);
}
public static void main(String[] args) {
Solution2 solution = new Solution2();
int max = solution.integerBreak(9);
System.out.println(max);
}
}
Python 代碼：動態(tài)規(guī)劃，注意：將 進(jìn)行分解的時(shí)候，以
為例：
與
是一個(gè)解，
與
的分解的結(jié)果也是一個(gè)解。
class Solution:
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
product = [0] * (n + 1)
product[1] = 1
for i in range(2, n + 1):
product_max = 0
for j in range(1, i):
product_max = max(j * product[i - j], product_max, j * (i - j))
product[i] = product_max
return product[n]
Java 代碼：
/**
* 動態(tài)規(guī)劃的解法
* Created by liwei on 17/10/3.
*/
public class Solution3 {
private int[] memory;
public int integerBreak(int n) {
memory = new int[n + 1];
memory[0] = 0;
memory[1] = 1;
for (int i = 2; i <= n; i++) {
int maxValue = -1;
for (int j = 1; j <= i - 1; j++) {
maxValue = max3(maxValue, j * (i - j), j * memory[i - j]);
}
memory[i] = maxValue;
}
return memory[n];
}
private int max3(int num1, int num2, int num3) {
int temp = Integer.max(num1, num2);
return Integer.max(temp, num3);
}
public static void main(String[] args) {
Solution3 solution = new Solution3();
int max = solution.integerBreak(9);
System.out.println(max);
}
}
總結(jié)：先研究遞歸解構(gòu)，再記憶化搜索，最后實(shí)現(xiàn)使用“動態(tài)規(guī)劃”。即先“自頂向下”思考，再“自底向上”實(shí)現(xiàn)。
思路3：貪心。這個(gè)規(guī)律要寫到 左右才能看清楚。
Python 代碼：貪心算法：1、能拆出 3 ，就盡量拆出 3；2、最多拆出 2 個(gè) 2。
最優(yōu)子結(jié)構(gòu)
下面我們引入一個(gè)新的概念：最優(yōu)子結(jié)構(gòu)。
什么是“最優(yōu)子結(jié)構(gòu)”？
我們通過求解子問題得到的最優(yōu)解，組成了我們規(guī)模更大的原問題的最優(yōu)解，這樣的動態(tài)規(guī)劃問題，我們稱之為具有“最優(yōu)子結(jié)構(gòu)”。
動態(tài)規(guī)劃問題通常應(yīng)用的場景是：我們直接求解這個(gè)問題感覺難度較大，但是我們把這個(gè)問題拆分為規(guī)模更小的問題的時(shí)候，這個(gè)問題的解通常也就能夠找到，這樣的解決問題的實(shí)現(xiàn)通常都要借助遞歸來實(shí)現(xiàn)。
下面完成一些練習(xí)，重點(diǎn)體會什么是“最優(yōu)子結(jié)構(gòu)”。
練習(xí)
練習(xí)1：LeetCode 第 279 題：完全平方數(shù)
傳送門：279. 完全平方數(shù)。
給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如
1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少。示例 1:
輸入: n = 12 輸出: 3 解釋: 12 = 4 + 4 + 4.示例 2:
輸入: n = 13 輸出: 2 解釋: 13 = 4 + 9.
分析：這個(gè)問題的關(guān)鍵就在于“拆”，既然可以“拆”成多個(gè)的情況，那么最基本的情況就是“拆”成兩個(gè)，這兩個(gè)中，有一個(gè)是“干凈”的完全平方數(shù)，還有一個(gè)是沒有被“拆”干凈的數(shù)（對于小的數(shù)我們?nèi)丝梢砸谎劭闯?，?jì)算機(jī)看不出），所以還要繼續(xù)“拆”。所以遞歸結(jié)構(gòu)是這樣的：
例如：如果自己是完全平方數(shù)，就返回 。否則就是如下所有情況的最小值，我們以
為例進(jìn)行說明：
得到的解為
，其實(shí)就是 第 2 行和第 3 行的情況。
再以 為例：
得到的解也為
，看第
行就知道了。
特別注意：剩余的那個(gè)數(shù)如果等于 是完全可以的。我們定義這個(gè)問題中
和小于
的時(shí)候，解全部為
。這一點(diǎn)也是非常合理的，因?yàn)樾∮诘扔?
的數(shù)，都不能表示成“正整數(shù)”的完全平方數(shù)的和。此時(shí)當(dāng)前考慮的這個(gè)數(shù)，就一定是完全平方數(shù)，直接返回
就可以了。例如：
Java 代碼：
代碼實(shí)現(xiàn)要注意的地方：
1、因?yàn)榇蟮闹狄蕾囆〉闹担郧蠼? 會依賴比它小的值，這是設(shè)立外層循環(huán)的原因；
2、內(nèi)層循環(huán)的終止條件是 i - j * j >= 0，體會這里 = 0 是為什么；
3、既然是求最小值，默認(rèn)值就應(yīng)該是一個(gè)很大的值，但其實(shí)，最大的值不會超過 。
注意到，結(jié)果最多是 4。
Java 代碼：
import java.util.Arrays;
// 與 Solution2 是同一種寫法
public class Solution3 {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, 4);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; i - j * j >= 0; j++) {
dp[i] = Math.min(dp[i], 1 + dp[i - j * j]);
}
}
return dp[n];
}
public static void main(String[] args) {
Solution3 solution3 = new Solution3();
int numSquares = solution3.numSquares(12);
System.out.println(numSquares);
}
}
還可以使用廣度優(yōu)先遍歷完成：
下面這篇文章中的動畫清晰地展示了使用“廣度優(yōu)先遍歷”的方法。傳送門：圖解LeetCode第 279 號問題： 完全平方數(shù)。
注意：BFS 在圖論中建模的模板寫法。
1、使用隊(duì)列；
2、使用一個(gè)數(shù)組，表示是否訪問過。
Python 代碼：使用圖的廣度優(yōu)先遍歷
class Solution:
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
marked = [False for _ in range(n)]
queue = [(0, n)]
while queue:
level, top = queue.pop(0)
level += 1
start = 1
while True:
residue = top - start * start
if residue == 0:
return level
elif residue < 0:
break
else:
# 注意這里，如果訪問過，路徑肯定更長
# 所以只考慮沒有訪問過的情況
if not marked[residue]:
queue.append((level, residue))
marked[residue] = True
start += 1
Java 代碼：
import java.util.LinkedList;
// https://leetcode-cn.com/problems/perfect-squares/description/
// 廣度優(yōu)先遍歷
public class Solution {
// 使用 BFS 來解決這個(gè)問題
public int numSquares(int n) {
assert n > 0;
boolean[] visited = new boolean[n + 1];
LinkedList<Integer[]> queue = new LinkedList<>();
queue.addLast(new Integer[]{n, 0});
visited[n] = true;
int curNum;
int curStep;
while (!queue.isEmpty()) {
Integer[] pair = queue.removeFirst();
curNum = pair[0];
curStep = pair[1];
curStep++;
for (int i = 1; ; i++) {
int next = curNum - i * i;
if (next < 0) {
break;
}
if (!visited[next]) {
if (next == 0) {
return curStep;
}
queue.addLast(new Integer[]{next, curStep});
// 只要添加到隊(duì)列中，說明我們已經(jīng)考慮過，就沒有必要再添加到隊(duì)列中
visited[next] = true;
}
}
}
// 正常情況下是不會走到這句的
throw new IllegalArgumentException("參數(shù)錯(cuò)誤");
}
public static void main(String[] args) {
int n = 7168;
Solution s = new Solution();
int numSquares = s.numSquares(n);
System.out.println(numSquares);
}
}
練習(xí)2：LeetCode 第 91 題：解碼方法
傳送門：解碼方法。
要求：一條包含字母
A-Z的消息通過以下方式進(jìn)行了編碼：'A' -> 1 'B' -> 2 ... 'Z' -> 26給定一個(gè)只包含數(shù)字的非空字符串，請計(jì)算解碼方法的總數(shù)。
示例 1:
輸入: "12" 輸出: 2 解釋: 它可以解碼為 "AB"（1 2）或者 "L"（12）。示例 2:
輸入: "226" 輸出: 3 解釋: 它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
思路：拿具體的例子分析，比如：。假設(shè)我們已經(jīng)解決了
dp[0] 和 dp[1] ，從 dp[2] 開始考慮，分析 num[2]：
1、如果 num[2] 不等于 ，那么
dp[2] 的情況和 dp[1] 是一樣的，完成編碼，這是一種情況；
2、如果 num[2] 跟前面的 num[1] 合起來能夠組成一個(gè)字母，那么 dp[2] 和 dp[0] 是一樣的，完成編碼，這是一種情況。
兩種情況都能完成編碼，求總數(shù)，其實(shí)就是他們的和，這里其實(shí)是加法計(jì)數(shù)原理的應(yīng)用。
Python 代碼：
class Solution:
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
l = len(s)
if l == 0:
return 0
if l == 1:
return 1 if s[0] != '0' else 0
dp = [0 for _ in range(l)]
dp[0] = 1 if s[0] != '0' else 0
for i in range(1, l):
if s[i] != '0':
# 如果不是 '0' ，那么 s[i] 就可以編碼，所以 cur 就至少是 dp[i-1]
dp[i] += dp[i - 1]
if 9 < int(s[i - 1:i + 1]) < 27:
# 可以和前面的數(shù)字組成一個(gè)編碼
# 這個(gè)判斷是在寫出 dp[i] += dp[i - 2] 以后，看出數(shù)組下標(biāo)會越界，而增加的討論
if i - 2 < 0:
# 12
dp[i] += 1
else:
dp[i] += dp[i - 2]
return dp[l - 1]
Python 代碼：
class Solution:
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
l = len(s)
if l == 0:
return 0
dp = [1] + [0] * l
if s[0] == '0':
dp[1] = 0
else:
dp[1] = 1
for i in range(1, l):
if s[i] != '0':
dp[i + 1] += dp[i]
if s[i - 1] != '0' and int(s[i - 1:i + 1]) < 27:
dp[i + 1] += dp[i - 1]
return dp[-1]
說明：上面這段代碼 dp[0] = 1 是故意這么定義的，為了防止像上一版代碼那樣的討論。
記憶化遞歸的寫法，我沒有寫好：
http://songhuiming.github.io/pages/2018/03/11/leetcode-91-decode-ways/
http://songhuiming.github.io/pages/2018/03/11/leetcode-91-decode-ways/
http://songhuiming.github.io/pages/2018/03/11/leetcode-91-decode-ways/
花花醬：這位哥們錄制了所有 LeetCode 解法的視頻和解題報(bào)告。
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-91-decode-ways/
Java 解法，看起來很簡潔：
http://www.itdecent.cn/p/edd9da18eb01
練習(xí)3：LeetCode 第 62 題：不同路徑
傳送門：英文網(wǎng)址：62. Unique Paths ，中文網(wǎng)址：62. 不同路徑 。
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問總共有多少條不同的路徑？
LeetCode 第 62 題：不同路徑
例如，上圖是一個(gè)7 x 3 的網(wǎng)格。有多少可能的路徑？
說明：m 和 n 的值均不超過 100。
示例 1:
輸入: m = 3, n = 2 輸出: 3 解釋: 從左上角開始，總共有 3 條路徑可以到達(dá)右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右示例 2:
輸入: m = 7, n = 3 輸出: 28
思路1：機(jī)器人一定會走 步，即從
中挑出
步向下走即可，即
為所求。
Python 代碼：
class Solution(object):
def __factorial(self, n):
res = 1
while n > 1:
res *= n
n -= 1
return res
def __combination(self, m, n):
"""
從 n 個(gè)物品里選出 m 個(gè)物品的組合數(shù)
:param m:
:param n:
:return:
"""
return self.__factorial(n) // (self.__factorial(m) * self.__factorial(n - m))
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
return self.__combination(m - 1, m + n - 2)
if __name__ == '__main__':
m = 7
n = 3
solution = Solution()
result = solution.uniquePaths(m, n)
print(result)
思路2：特別注意到其實(shí)在左邊第一行和上邊第一行，肯定都為 ，還有就是新一行的值只與上一行有關(guān)，所以我們完全可以只設(shè)置一維數(shù)組，將這道題完成。其實(shí)使用
個(gè)變量也可以完成。
Python 代碼1：記憶化搜索，
class Solution:
def __init__(self):
self.cached = None
def __path(self, i, j):
if self.cached[i][j] != 0:
return self.cached[i][j]
if i == 0 and j == 0:
return 1
path_ways = 0
if i == 0:
path_ways = self.__path(0, j - 1)
elif j == 0:
path_ways = self.__path(i - 1, 0)
else:
path_ways = self.__path(i, j - 1) + self.__path(i - 1, j)
self.cached[i][j] = path_ways
return path_ways
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
self.cached = [[0 for _ in range(n)] for _ in range(m)]
return self.__path(m - 1, n - 1)
用測試用例得到的緩存數(shù)組：[[0, 1, 1, 1], [1, 2, 3, 4], [1, 3, 6, 10], [1, 4, 10, 20], [1, 5, 15, 35]]。
Python 代碼：動態(tài)規(guī)劃
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = 1
for i in range(m):
for j in range(n):
if i == 0:
if j == 0:
continue
dp[0][j] = dp[0][j - 1]
elif j == 0:
dp[i][0] = dp[i - 1][0]
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[- 1][- 1]
動態(tài)規(guī)劃得到的 dp 數(shù)組：[[1, 1, 1, 1], [1, 2, 3, 4], [1, 3, 6, 10], [1, 4, 10, 20], [1, 5, 15, 35]]。下面介紹更節(jié)省空間的一種解法：
我是如何想到的：把緩存數(shù)組抄一遍，或者自己把矩陣畫出來，就能知道這個(gè)數(shù)組怎么來的。每一行，只依賴上一行的結(jié)果，我們完全可以用一行來逐步更新。第 1 個(gè)元素肯定是 1，并且第 1 行元素肯定全是 1。有點(diǎn)“背包問題”的意思：節(jié)約了空間。
Python 代碼：
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m == 0:
return 0
dp = [1] * n
for row in range(m - 1):
for col in range(1, n):
dp[col] += dp[col - 1]
return dp[-1]
Python 代碼：與上一版等價(jià)
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [1] * n
for i in range(1, m):
for i in range(1, n): # 從索引 2 開始走就行了
dp[i] = dp[i] + dp[i - 1]
return dp[-1]
練習(xí)4：LeetCode 第 63 題：不同路徑 II
傳送門：英文網(wǎng)址：63. Unique Paths II ，中文網(wǎng)址：63. 不同路徑 II 。
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
網(wǎng)格中的障礙物和空位置分別用
1和0來表示。LeetCode 第 63 題：不同路徑 II說明：m 和 n 的值均不超過 100。
示例 1:
輸入: [ [0,0,0], [0,1,0], [0,0,0] ] 輸出: 2 解釋: 3x3 網(wǎng)格的正中間有一個(gè)障礙物。 從左上角到右下角一共有 2 條不同的路徑： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
Python 代碼：
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
if m == 0:
return 0
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1:
return 0
dp = [0] * n
# 這一步不要忘記了
dp[0] = 1
# 再寫后面幾行
for row in range(m):
for col in range(n):
# 【就分下面這兩種情況就可以了】
if obstacleGrid[row][col] == 1:
dp[col] = 0
elif col > 0:
dp[col] += dp[col - 1]
else:
# 第 0 列不是 0 就是 1
# 0 的情況首先判斷了
# 什么都不做
pass
return dp[-1]
Python 代碼：與上一版等價(jià)的寫法
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
if m == 0:
return 0
n = len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
if obstacleGrid[0][0] == 1:
return 0
else:
dp[0][0] = 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
continue
if i == 0:
if j == 0:
continue
dp[0][j] = dp[0][j - 1]
elif j == 0:
dp[i][0] = dp[i - 1][0]
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
（本節(jié)完）
