LeetCode入門指南 之 動態規劃思想
- 2021 年 9 月 1 日
- 筆記
- leetcode, LeetCode入門指南, 算法, 面試
推薦學習labuladong大佬的動態規劃系列文章：先弄明白什麼是動態規劃即可，不必一次看完。接着嘗試自己做，沒有思路了再回過頭看相應的文章。
動態規劃一般可以由 遞歸 + 備忘錄 一步步轉換而來，不必被名字唬住。通常只要找到狀態轉移方程問題就解決了一大半，至於狀態的選擇只要題目做多了自然就會形成經驗，通常是問什麼就設什麼為狀態。
常見四種類型
- Matrix DP (10%)
- Sequence (40%)
- Two Sequences DP (40%)
- Backpack (10%)
注意：
- 貪心算法大多題目靠背答案，所以如果能用動態規劃就盡量用動規，不用貪心算法。一般可以先嘗試用動態規劃，如果超時再用貪心。
1、矩陣類型（10%）
120. 三角形最小路徑和
給定一個三角形
triangle，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。相鄰的結點 在這裡指的是 下標 與 上一層結點下標 相同或者等於 上一層結點下標 + 1 的兩個結點。也就是說，如果正位於當前行的下標
i，那麼下一步可以移動到下一行的下標i或i + 1。輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 輸出：11 解釋：如下面簡圖所示： 2 3 4 6 5 7 4 1 8 3 自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。
class Solution {
public int minimumTotal(List<list<integer>> triangle) {
/**
* 狀態：當前位置到底部最小路徑和
* 狀態轉移方程：dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i + 1]j[j + 1])；i為行，j為列
* base case：最後一行dp[i][j] = triangle[i][j];
*/
int m = triangle.size();
int[][] dp = new int[m][m];
//base case
for (int i = 0; i < m; i++) {
dp[m - 1][i] = triangle.get(m - 1).get(i);
}
//倒數第二行開始轉移（遞推）
for (int i = m - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
}
}
return dp[0][0];
}
}
該解法空間複雜度為dp表的大小，為 O(N2) 。容易發現當前行dp的值只與下一行的相關，我們不必將所有dp值通過二維數組存下來，可以通過復用一個一維數組來實現。
class Solution {
public int minimumTotal(List<list<integer>> triangle) {
int m = triangle.size();
int[] dp = new int[m];
//base case，先只存最後一行的dp值
for (int i = 0; i < m; i++) {
dp[i] = triangle.get(m - 1).get(i);
}
//倒數第二行開始轉移（遞推）
for (int i = m - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
}
64. 最小路徑和
給定一個包含非負整數的
m x n網格grid，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。說明：每次只能向下或者向右移動一步。
示例 1：
輸入：grid = [[1,3,1],[1,5,1],[4,2,1]] 輸出：7 解釋：因為路徑 1→3→1→1→1 的總和最小。
思路：動態規劃，和上一題相似。
-
狀態：起點到當前結點的最小路徑和
-
轉移方程：起點到當前結點最小路徑和
dp[i][j]等於：min(起點到其相鄰左結點最小路徑和dp[i][j - 1]，起點到其相鄰上結點最小路徑和dp[i - 1][j]) + 當前結點值grid[i][j] -
base case:
dp[0][0] = grid[0][0]; 第一行dp[0][x]都為其相鄰左結點dp[0][x -1]+ 自身結點值grid[0][x],x >= 1;第一列dp[x][0]都為其相鄰上結點dp[x - 1][0]+ 自身結點值grid[x][0],x >= 1。
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
//從左上角到i, j的最短路徑和
int[][] dp = new int[m][n];
//base case
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
//轉移方程
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp [i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
62. 不同路徑
一個機械人位於一個 m x n 網格的左上角 （起始點在下圖中標記為 「Start」 ）。
機械人每次只能向下或者向右移動一步。機械人試圖達到網格的右下角（在下圖中標記為 「Finish」 ）。
問總共有多少條不同的路徑？
示例 1：
輸入：m = 3, n = 7
輸出：28
思路：動態規劃
-
狀態：從起點到當前結點的不同路徑數。
-
轉移方程：起點到當前點的不同路徑數
dp[i][j]等於：起點到當前結點相鄰左結點dp[i][j - 1]和相鄰上結點dp[i - 1][j]不同路徑數之和。 -
base case：第0行
dp[0][x]和0列dp[x][0]都為1，前者只能通過其相鄰左節點到達，後者只能通過相鄰上結點到達。
class Solution {
public int uniquePaths(int m, int n) {
//狀態
int dp[][] = new int[m][n];
//base case
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
dp[i][0] = 1;
}
//轉移方程
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
}
63. 不同路徑 II
一個機械人位於一個 m x n 網格的左上角 （起始點在下圖中標記為「Start」 ）。
機械人每次只能向下或者向右移動一步。機械人試圖達到網格的右下角（在下圖中標記為「Finish」）。
現在考慮網格中有障礙物。那麼從左上角到右下角將會有多少條不同的路徑？
網格中的障礙物和空位置分別用
1和0來表示。示例 1：
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 輸出：2 解釋： 3x3 網格的正中間有一個障礙物。 從左上角到右下角一共有 2 條不同的路徑： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int dp[][] = new int[m][n];
// base case
if (obstacleGrid[0][0] != 1) { // 起點不是障礙
dp[0][0] = 1;
}
for (int i = 1; i < n; i++) {
if (obstacleGrid[0][i] != 1) {
dp[0][i] = dp[0][i - 1];
}
}
for (int i = 1; i < m; i++) {
if (obstacleGrid[i][0] != 1) {
dp[i][0] = dp[i - 1][0];
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] != 1) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
}
return dp[m - 1][n - 1];
}
}
2、序列類型（40%）
70. 爬樓梯
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數。
思路：動態規劃
-
狀態：從第0個台階跳到當前台階的不同方式
-
轉移方程：第0個台階到當前台階的不同方式
dp[i]等於：第0個台階到當前台階下面兩個台階的不同方式之和(dp[i - 1] + dp[i - 2]) -
base case:
dp[0] = dp[1] = 1
class Solution {
public int climbStairs(int n) {
//狀態：從第0個台階跳到當前台階的不同方式
int[] dp = new int[n + 1];
//base case
dp[0] = 1;
dp[1] = 1;
//轉移方程
for (int i = 2; i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
55. 跳躍遊戲
給定一個非負整數數組
nums，你最初位於數組的 第一個下標 。數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最後一個下標。
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
//起始位置能否跳至當前位置
boolean[] dp = new boolean[len];
//base case
dp[0] = true;
//轉移方程：i前面所有的點只要有一個能跳到當前結點就說明當前結點可達
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && (j + nums[j] >= i)) {
dp[i] = true;
break;
}
}
}
return dp[len - 1];
}
}
45. 跳躍遊戲 II
給定一個非負整數數組，你最初位於數組的第一個位置。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數到達數組的最後一個位置。
說明:
假設你總是可以到達數組的最後一個位置。
class Solution {
//狀態：從下標為0的位置跳到i所需的最小跳躍次數
//轉移方程：從下標為0的位置跳到i所需的最小跳躍次數等於：i前面一次跳躍就能到達i的所有結點中的最小dp值 + 1
//base case:dp[0] = 0
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, n); //最多跳n - 1次，求最小值，先將其初始化為足夠大
//base case
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] + j >= i) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
}
132. 分割迴文串 II
給你一個字符串
s，請你將s分割成一些子串，使每個子串都是迴文。返回符合要求的 最少分割次數 。
class Solution {
// 狀態：從頭字符到以當前字符結尾形成的字符串分割成迴文子串需要的最少分割次數
// 轉移方程：dp[i] = min(dp[i], dp[j] + 1), j < i 且 [j + 1, i]區間的子串為迴文子串
// base case:dp[0] = 0
public int minCut(String s) {
int len = s.length();
// 先使用動態規劃獲得任意兩個區間的字符串是否為迴文字符串
boolean[][] isPalindrome = getPalindrome(s);
// 求最小值，先初始化足夠大（最多s最多分割 len - 1 次）
int[] dp = new int[len];
Arrays.fill(dp, len);
for (int j = 0; j < len; j++) {
//無需分割
if (isPalindrome[0][j]) {
dp[j] = 0;
continue;
}
for (int i = 1; i <= j; i++) {
if (isPalindrome[i][j]) {
dp[j] = Math.min(dp[j], dp[i - 1] + 1);
}
}
}
return dp[len - 1];
}
private boolean[][] getPalindrome(String s) {
int len = s.length();
// 區間i,j的字符串是否為迴文字符串(左右都為閉區間)
boolean[][] dp = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
}
}
}
return dp;
}
}
300. 最長遞增子序列
給你一個整數數組
nums，找到其中最長嚴格遞增子序列的長度。子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其餘元素的順序。例如，
[3,6,2,7]是數組[0,3,1,6,2,2,7]的子序列。
-
思路：動態規劃
-
狀態：以當前字符結尾的字符串中最長遞增子序列的長度
-
轉移方程：
dp[i] = max(dp[j] + 1, dp[i])，其中j < i且nums[j] < nums[i] -
base case：
dp[i] = 1
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
// dp[i] 表示以當前字符結尾的字符串中最長遞增子序列的長度
int[] dp = new int[len];
//base case, 最少長度為1
Arrays.fill(dp, 1);
int maxLen = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}
139. 單詞拆分
給定一個非空字符串 s 和一個包含非空單詞的列表 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現的單詞。
說明：
- 拆分時可以重複使用字典中的單詞。
- 你可以假設字典中沒有重複的單詞。
class Solution {
public boolean wordBreak(String s, List<string> wordDict) {
Set<string> set = new HashSet<>();
for (String str : wordDict) {
set.add(str);
}
int len = s.length();
// 狀態： s 中前 i 個字符能否拆分成功
boolean[] dp = new boolean[len + 1];
// base case
dp[0] = true;
// 狀態轉移
// s[0, i]能否被分割取決於:區間[j, i]是否屬於set和dp[j]的值(前j個字符 [0, j - 1] 能否被分割)，j <= i
for (int i = 1; i < len + 1; i++) {
for (int j = 0; j < i; j++) {
if (set.contains(s.substring(j, i)) && dp[j]) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}
推薦題解：「手畫圖解」剖析三種解法: DFS, BFS, 動態規劃 |139.單詞拆分
3、雙序列（40%）
1143. 最長公共子序列
給定兩個字符串
text1和text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回0。一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）後組成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
//狀態：text1前m個和text2前n個字符的最長公共子序列長度
int[][] dp = new int[m + 1][n + 1];
//base case, dp[x][0] = dp[0][x] = 0; 默認值即可
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
//如果當前兩個字符相同
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
//不等說明有其中一個字符不在最長公共子序列中
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
72. 編輯距離
給你兩個單詞
word1和word2，請你計算出將word1轉換成word2所使用的最少操作數 。你可以對一個單詞進行如下三種操作：
- 插入一個字符
- 刪除一個字符
- 替換一個字符
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
//word1 前m個字符和 word2 前n個字符之間的編輯距離，注意下標對應關係
int[][] dp = new int[m + 1][n + 1];
//base case
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= n; i++) {
dp[0][i] = i;
}
// 狀態轉移
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 最後一個字符相等
if (word1.charAt(i - 1) == word2.charAt(j -1)) {
dp[i][j] = dp[i - 1][j - 1];
// 不等則 在word1後增加word2的最後一個字符、刪除word1中最後一個字符，或將word1最後一個字符修改成和word2最後一個字符相同；取代價最小的一個
} else {
dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[m][n];
}
}
4、零錢和背包（10%）
322. 零錢兌換
給定不同面額的硬幣
coins和一個總金額amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回-1。你可以認為每種硬幣的數量是無限的。
class Solution {
public int coinChange(int[] coins, int amount) {
// 狀態：dp[i] 表示湊夠i需要的最少硬幣數
int[] dp = new int[amount + 1];
// 求最小值，先初始為足夠大。(若能湊成，最多需要amount枚硬幣)
Arrays.fill(dp, amount + 1);
// base case
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
// 當前背包（總金額）若能裝下物品（硬幣面額）
if (i >= coins[j]) {
dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
}
}
}
return dp[amount] >= amount + 1 ? -1 : dp[amount];
}
}
92 · 背包問題
在 n 個物品中挑選若干物品裝入背包，最多能裝多滿？假設背包的大小為 m，每個物品的大小為 A[i]
public class Solution {
public int backPack(int m, int[] A) {
int n = A.length;
//背包容量為m，有前n個物品，能否將背包裝滿
boolean[][] dp = new boolean[m + 1][n + 1];
//base case, 背包容量為0時dp[0][x] = true; 背包容量大於0但沒有物品時dp[x][0] = false，x > 0
for (int i = 0; i <= n; i++) {
dp[0][i] = true;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
//如果前 j - 1 個就可以裝滿 i
if (dp[i][j - 1]) {
dp[i][j] = true;
} else if (i >= A[j - 1] && dp[i - A[j - 1]][j - 1]) {
dp[i][j] = true;
}
}
}
for (int i = m; i > 0; i--) {
if (dp[i][n]) {
return i;
}
}
return 0;
}
}
125 · 背包問題 II
有
n個物品和一個大小為m的背包. 給定數組A表示每個物品的大小和數組V表示每個物品的價值. 問最多能裝入背包的總價值是多大?
public class Solution {
public int backPackII(int m, int[] A, int[] V) {
int n = A.length;
//背包容量為m，有前n個物品時能裝入的最大價值
int[][] dp = new int[m + 1][n + 1];
//base case, dp[x][0] = dp[0][x] = 0
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
//當前背包能容納
if (i >= A[j - 1]) {
dp[i][j] = Math.max(dp[i - A[j - 1]][j - 1] + V[j - 1], dp[i][j - 1]);
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[m][n];
}
}
</list
