首先我們來看 LeetCode 第 343 題捣炬，其實動態(tài)規(guī)劃也包含了暴力求解，只不過我們按照一定規(guī)律踊东，并且是在假設(shè)規(guī)模更小的問題已經(jīng)得到解決的情況下产徊，得到了我們原先要解決的那個規(guī)模的問題的解，我個人認為技巧在于“分類討論”井赌，而“分類討論”的關(guān)鍵就在于“不重不漏”谤逼。
例題1：LeetCode 第 343 號問題：Integer Break
傳送門：343. 整數(shù)拆分。
給定一個正整數(shù) n仇穗，將其拆分為至少兩個正整數(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：回溯瓷马，也可以理解為“暴力搜索”。遍歷將一個數(shù)做分割的所有可能性跨晴，時間復(fù)雜度是 欧聘。
思路2：關(guān)鍵：“至少分割成兩個部分”。分析這個問題的遞歸結(jié)構(gòu)：“至少分割成兩個正整數(shù)” = “一個正整數(shù)” + “另一個還沒有分割的正整數(shù)”端盆。這道題解題的關(guān)鍵在于“至少分割成兩個正整數(shù)”怀骤，從這個角度出發(fā)，就能夠得到我們“自頂向下”思考這個問題的路徑焕妙，進而使用“記憶化搜索”或者“動態(tài)規(guī)劃”得到原問題的解蒋伦。
畫出如下樹形結(jié)構(gòu)：
發(fā)現(xiàn)有大量重疊子問題。
定義狀態(tài)： 表示正整數(shù)
經(jīng)過分割以后得到的數(shù)字乘積的最大值焚鹊。
則狀態(tài)轉(zhuǎn)移方程是：
從這個過程中體會：1痕届、原問題的解是規(guī)模更小的子問題的解的組合；2末患、“狀態(tài)”定義好了研叫，上面的那個等式，其實就是“狀態(tài)轉(zhuǎn)移方程”璧针。
對于每一個狀態(tài)而言嚷炉，還要再比較“不再繼續(xù)分割”和“繼續(xù)分割”，取當(dāng)中的最大值探橱。由上面的思路申屹，我們可以寫一個遞歸方法。
下面隧膏，我們給出 3 個解答哗讥，這 3 種方式的解答體現(xiàn)了我們思考“線性規(guī)劃”問題的一般步驟。
Java 代碼：不含記憶化搜索的遞歸
/**
* 沒有記憶化搜索的遞歸解法
* 這個版本提交給 LeetCode 是通不過的
* Created by liwei on 17/10/3.
*/
public class Solution {
public int integerBreak(int n) {
int res = breakInteger(n);
return res;
}
/**
* 將 n 進行分割（至少分割成兩個部分）胞枕，可以獲得乘積的最大值
* @param num
* @return 將 n 進行分割得到的乘積最大值
*/
private int breakInteger(int num) {
if (num == 1) {
return 1;
}
int res = 0; // 這個初始值可以設(shè)置為 0 嗎杆煞，1 行不行？
for (int i = 1; i < num; i++) {
// 關(guān)鍵之處：狀態(tài)轉(zhuǎn)移方程曲稼，其中 i * (num - i) 這一步很關(guān)鍵索绪，千萬不能漏掉
// 這里有一個陷阱，就是不能忽略能不能繼續(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 進行分割得到的乘積最大值
private int breakInteger(int num) {
if (num == 1) {
return 1;
}
if (memory[num] == -1) {
int res = 0; // 這個初始值可以設(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ī)劃凳寺，注意：將 進行分解的時候，以
為例：
與
是一個解彤侍，
與
的分解的結(jié)果也是一個解肠缨。
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)，再記憶化搜索盏阶，最后實現(xiàn)使用“動態(tài)規(guī)劃”晒奕。即先“自頂向下”思考，再“自底向上”實現(xiàn)名斟。
思路3：貪心脑慧。這個規(guī)律要寫到 左右才能看清楚。
Python 代碼：貪心算法：1砰盐、能拆出 3 闷袒，就盡量拆出 3；2岩梳、最多拆出 2 個 2囊骤。
最優(yōu)子結(jié)構(gòu)
下面我們引入一個新的概念：最優(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)用的場景是：我們直接求解這個問題感覺難度較大激况，但是我們把這個問題拆分為規(guī)模更小的問題的時候作彤，這個問題的解通常也就能夠找到，這樣的解決問題的實現(xiàn)通常都要借助遞歸來實現(xiàn)乌逐。
下面完成一些練習(xí)竭讳，重點體會什么是“最優(yōu)子結(jié)構(gòu)”。
練習(xí)
練習(xí)1：LeetCode 第 279 題：完全平方數(shù)
傳送門：279. 完全平方數(shù)浙踢。
給定正整數(shù) n绢慢，找到若干個完全平方數(shù)（比如
1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個數(shù)最少洛波。示例 1:
輸入: n = 12 輸出: 3 解釋: 12 = 4 + 4 + 4.示例 2:
輸入: n = 13 輸出: 2 解釋: 13 = 4 + 9.
分析：這個問題的關(guān)鍵就在于“拆”胰舆，既然可以“拆”成多個的情況，那么最基本的情況就是“拆”成兩個蹬挤，這兩個中缚窿，有一個是“干凈”的完全平方數(shù)，還有一個是沒有被“拆”干凈的數(shù)（對于小的數(shù)我們?nèi)丝梢砸谎劭闯鲅姘猓嬎銠C看不出）倦零，所以還要繼續(xù)“拆”误续。所以遞歸結(jié)構(gòu)是這樣的：
例如：如果自己是完全平方數(shù)，就返回 扫茅。否則就是如下所有情況的最小值蹋嵌，我們以
為例進行說明：
得到的解為
，其實就是 第 2 行和第 3 行的情況葫隙。
再以 為例：
得到的解也為
栽烂，看第
行就知道了。
特別注意：剩余的那個數(shù)如果等于 是完全可以的恋脚。我們定義這個問題中
和小于
的時候愕鼓，解全部為
。這一點也是非常合理的慧起，因為小于等于
的數(shù)菇晃，都不能表示成“正整數(shù)”的完全平方數(shù)的和。此時當(dāng)前考慮的這個數(shù)蚓挤，就一定是完全平方數(shù)磺送，直接返回
就可以了。例如：
Java 代碼：
代碼實現(xiàn)要注意的地方：
1灿意、因為大的值要依賴小的值估灿，所以求解 會依賴比它小的值，這是設(shè)立外層循環(huán)的原因缤剧；
2馅袁、內(nèi)層循環(huán)的終止條件是 i - j * j >= 0，體會這里 = 0 是為什么荒辕；
3汗销、既然是求最小值，默認值就應(yīng)該是一個很大的值抵窒，但其實弛针，最大的值不會超過 。
注意到李皇，結(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、使用隊列卓囚；
2瘾杭、使用一個數(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 來解決這個問題
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});
// 只要添加到隊列中，說明我們已經(jīng)考慮過页徐，就沒有必要再添加到隊列中
visited[next] = true;
}
}
}
// 正常情況下是不會走到這句的
throw new IllegalArgumentException("參數(shù)錯誤");
}
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的消息通過以下方式進行了編碼：'A' -> 1 'B' -> 2 ... 'Z' -> 26給定一個只包含數(shù)字的非空字符串，請計算解碼方法的總數(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] 合起來能夠組成一個字母郑叠，那么 dp[2] 和 dp[0] 是一樣的，完成編碼明棍，這是一種情況乡革。
兩種情況都能完成編碼侠姑，求總數(shù)巫湘，其實就是他們的和，這里其實是加法計數(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ù)字組成一個編碼
# 這個判斷是在寫出 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 解法的視頻和解題報告。
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-91-decode-ways/
Java 解法娃殖，看起來很簡潔：
http://www.reibang.com/p/edd9da18eb01
練習(xí)3：LeetCode 第 62 題：不同路徑
傳送門：英文網(wǎng)址：62. Unique Paths 值戳，中文網(wǎng)址：62. 不同路徑 。
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）炉爆。
機器人每次只能向下或者向右移動一步堕虹。機器人試圖達到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）卧晓。
問總共有多少條不同的路徑？
LeetCode 第 62 題：不同路徑
例如赴捞，上圖是一個7 x 3 的網(wǎng)格逼裆。有多少可能的路徑？
說明：m 和 n 的值均不超過 100赦政。
示例 1:
輸入: m = 3, n = 2 輸出: 3 解釋: 從左上角開始胜宇，總共有 3 條路徑可以到達右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右示例 2:
輸入: m = 7, n = 3 輸出: 28
思路1：機器人一定會走 步恢着，即從
中挑出
步向下走即可桐愉，即
為所求。
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 個物品里選出 m 個物品的組合數(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：特別注意到其實在左邊第一行和上邊第一行掰派，肯定都為 从诲，還有就是新一行的值只與上一行有關(guān)，所以我們完全可以只設(shè)置一維數(shù)組靡羡，將這道題完成盏求。其實使用
個變量也可以完成。
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ù)組抄一遍纳像，或者自己把矩陣畫出來荆烈，就能知道這個數(shù)組怎么來的。每一行竟趾，只依賴上一行的結(jié)果憔购，我們完全可以用一行來逐步更新。第 1 個元素肯定是 1岔帽，并且第 1 行元素肯定全是 1玫鸟。有點“背包問題”的意思：節(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 代碼：與上一版等價
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 屎飘。
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）。
機器人每次只能向下或者向右移動一步贾费。機器人試圖達到網(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)格的正中間有一個障礙物导犹。 從左上角到右下角一共有 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 代碼：與上一版等價的寫法
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é)完）
