代碼隨想錄_動態規劃

代碼隨想錄

動態規劃

509.斐波那契數

509. 斐波那契數

斐波那契數 （通常用 F(n) 表示）形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定 n ，請計算 F(n) 。

思路: 動態規劃.

1.確定dp數組以及下標的含義: dp[i]的定義為：第i個數的斐波那契數值是dp[i]

2.確定遞推公式: dp[i] = dp[i - 1] + dp[i - 2];

3.dp數組如何初始化

dp[0] = 0;
dp[1] = 1;

4.確定遍歷順序: 從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依賴 dp[i - 1] 和 dp[i - 2]，那么遍歷的順序一定是從前到后遍歷的

5.舉例推導dp數組: 按照這個遞推公式dp[i] = dp[i - 1] + dp[i - 2]，我們來推導一下，當N為10的時候，dp數組應該是如下的數列：0 1 1 2 3 5 8 13 21 34 55

代碼:

class Solution {public int fib(int n) {// 1. 特殊判斷if(n <= 1) return n;// 2. 定義dp數組int[] dp = new int[n+1];// 3. 初始化dp[0] = 0;dp[1] = 1;// 4. 依照公式遍歷for(int i = 2;i <= n;i++) {dp[i] = dp[i-1] + dp[i-2];}// 5. 返回return dp[n];}
}

簡化:

class Solution {public int fib(int n) {// 1. 特殊判斷if(n <= 1) return n;// 2. 變量代替數組int a = 0,b = 1,sum = 0;// 3. 公式遍歷for(int i = 2;i <= n;i++) {sum = a + b;a = b;b = sum;}// 4. 返回return b;}
}

70.爬樓梯

70. 爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

思路: 動態規劃

爬到第n階: 先爬到第n-1階,再爬1階 / 先爬到第n-2階,再爬兩階以此遞歸

遞歸出口: 爬到第1階: 1種方法. 爬到第2階: 2種方法.

代碼: 遞推公式和斐波那契數相同, 也可以使用變量進行簡化

class Solution {public int climbStairs(int n) {// 下面直接對dp[2]操作, n<=1沒有dp[2],防止數組下標越界if(n <= 1) return n;// 1. 初始化dp數組int[] dp = new int[n+1];dp[1] = 1;dp[2] = 2;// 2. 根據遞推方式填充數組(i:第i階臺階. dp[i]:爬到第i階方式的種類)for(int i = 3;i <= n;i++) {dp[i] = dp[i-1] + dp[i-2];}// 3. 返回return dp[n];}
}

746.使用最小花費爬樓梯

746. 使用最小花費爬樓梯

給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。

你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。

請你計算并返回達到樓梯頂部的最低花費。

思路: 動態規劃

確定dp數組及下標含義: dp[i]: 到達第i臺階所花費的最少體力為dp[i]
確定遞推公式: 有兩種途徑得到dp[i], dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
dp數組如何初始化: 向前遞歸+題意: “你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。” 也就是說到達第 0 個臺階是不花費的，但從第0 個臺階往上跳的話，需要花費 cost[0]。所以初始化 dp[0] = 0，dp[1] = 0;
確定遍歷順序: 因為是模擬臺階，而且dp[i]由dp[i-1]dp[i-2]推出，所以是從前到后遍歷cost數組就可以了。
舉例推導dp數組

代碼:

class Solution {public int minCostClimbingStairs(int[] cost) {// 1. 創建dp數組int len = cost.length;int[] dp = new int[len+1];// 2. 初始化dp[0] = 0;dp[1] = 0;// 3. 根據公式遞推for(int i = 2;i <= len;i++) {dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);}// 4. 返回return dp[len];}
}

62.不同路徑

62. 不同路徑

一個機器人位于一個 m x n 網格的左上角（起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。

問總共有多少條不同的路徑？

示例 1：

輸入：m = 3, n = 7
輸出：28

思路: 動態規劃.

確定dp數組（dp table）以及下標的含義

 dp[i] [j] ：表示從（0 ，0）出發，到(i, j) 有dp[i] [j]條不同的路徑。

確定遞推公式

 想要求dp[i] [j]，只能有兩個方向來推導出來，即dp[i - 1] [j] 和 dp[i] [j - 1]。此時在回顧一下 dp[i - 1] [j] 表示啥，是從(0, 0)的位置到(i - 1, j)有幾條路徑，dp[i][j - 1]同理。那么很自然，dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]，因為dp[i] [j]只有這兩個方向過來。

dp數組的初始化

 如何初始化呢，首先dp[i] [0]一定都是1，因為從(0, 0)的位置到(i, 0)的路徑只有一條，那么dp[0][j]也同理。所以初始化代碼為：

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

確定遍歷順序

 這里要看一下遞推公式dp[i] [j] = dp[i - 1] [j] + dp[i] [j - 1]，dp[i] [j]都是從其上方和左方推導而來，那么從左到右一層一層遍歷就可以了。這樣就可以保證推導dp[i] [j]的時候，dp[i - 1] [j] 和 dp[i] [j - 1]一定是有數值的。

舉例推導dp數組

代碼:

class Solution {public int uniquePaths(int m, int n) {// 1. 建立dp數組int[][] dp = new int[m][n];// 2. 初始化for(int i = 0;i < m;i++) dp[i][0] = 1;for(int j = 0;j < n;j++) dp[0][j] = 1;// 3. 遍歷填充for(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}// 4. 返回return dp[m-1][n-1];}
}

63.不同路徑 II

63. 不同路徑 II

給定一個 m x n 的整數數組 grid。一個機器人初始位于 左上角（即 grid[0][0]）。機器人嘗試移動到 右下角（即 grid[m - 1][n - 1]）。機器人每次只能向下或者向右移動一步。

網格中的障礙物和空位置分別用 1 和 0 來表示。機器人的移動路徑中不能包含任何有障礙物的方格。

返回機器人能夠到達右下角的不同路徑數量。

測試用例保證答案小于等于 2 * 109。

示例 1：

輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

思路: 動態規劃, 具體同上一道. 注意要根據obstacleGrid[][]是否有障礙物來初始化dp, 障礙物所在地方及以下, 以右, 都無法再到達, 因此不需要再手動初始化, 默認為0即可.

代碼:

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {// 1. 創建dp數組int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];// 2. 根據obstacleGrid的障礙物分布進行初始化for(int i = 0;i < m && obstacleGrid[i][0] == 0;i++) dp[i][0] = 1;for(int j = 0;j < n && obstacleGrid[0][j] == 0;j++) dp[0][j] = 1;// 3. 按照公式填充dpfor(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {dp[i][j] = obstacleGrid[i][j] == 0 ? dp[i-1][j]+dp[i][j-1] : 0;}}// 4. 返回return dp[m-1][n-1];}
}

343.整數拆分

343. 整數拆分

給定一個正整數 n ，將其拆分為 k 個 正整數 的和（ k >= 2 ），并使這些整數的乘積最大化。

返回 你可以獲得的最大乘積 。

思路: 動態規劃.

確定dp數組（dp table）以及下標的含義
- dp[i]：分拆數字i，可以得到的最大乘積為dp[i]。
- dp[i]的定義將貫徹整個解題過程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！
確定遞推公式
- dp[i]最大乘積其實可以從1遍歷j，然后有兩種渠道得到dp[i].
  - j * (i - j) 直接相乘。
  - j * dp[i - j]，相當于是拆分(i - j)
dp的初始化
- 嚴格從dp[i]的定義來說，dp[0] dp[1] 就不應該初始化，也就是沒有意義的數值。
- dp[2] = 1，從dp[i]的定義來說，拆分數字2，得到的最大乘積是1
確定遍歷順序
- 先遍歷物品更好理解
舉例推到dp數組

代碼:

class Solution {public int integerBreak(int n) {// 1. 創建dp數組, i表示要拆分的數值, dp[i]表示拆分后正數乘積的最大值int[] dp = new int[n+1];// 2. 根據題意從2開始初始化dp[2] = 1;// 3. 從3開始拆分for(int i = 3;i <= n;i++) {// 外層控制當前要拆分的數值for(int j = 1;j <= i/2;j++) {// 內層進行拆分, 根據題意從j=1開始dp[i] = Math.max( dp[i] , Math.max(j*(i-j),j*dp[i-j]) );//                找最大值          拆分一次 繼續拆分}}// 4. 返回結果return dp[n];}
}

96.不同的二叉搜索樹

96. 不同的二叉搜索樹

給你一個整數 n ，求恰由 n 個節點組成且節點值從 1 到 n 互不相同的 二叉搜索樹 有多少種？返回滿足題意的二叉搜索樹的種數。

思路: 動態規劃

確定dp數組（dp table）以及下標的含義
- dp[i] ： 1到i為節點組成的二叉搜索樹的個數為dp[i]。
- 也可以理解是i個不同元素節點組成的二叉搜索樹的個數為dp[i] ，都是一樣的。
確定遞推公式
- dp[i] += dp[以j為頭結點左子樹節點數量] * dp[以j為頭結點右子樹節點數量]
- j相當于是頭結點的元素，從1遍歷到i為止。
- 所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為j為頭結點左子樹節點數量，i-j 為以j為頭結點右子樹節點數量
dp數組如何初始化
- 初始化，只需要初始化dp[0]就可以了，推導的基礎，都是dp[0]。從定義上來講，空節點也是一棵二叉樹，也是一棵二叉搜索樹，這是可以說得通的。
- 所以初始化dp[0] = 1
確定遍歷順序

for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}
}

- 首先一定是遍歷節點數，從遞歸公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，節點數為i的狀態是依靠 i之前節點數的狀態。那么遍歷i里面每一個數作為頭結點的狀態，用j來遍歷。
- 代碼如下：

舉例推導dp數組

代碼:

class Solution {public int numTrees(int n) {// 1. 建立dp數組int[] dp = new int[n+1];// 2. 初始化dp數組dp[0] = 1;// 3. 根據公式遞推for(int i = 1;i <= n;i++) {// 外層循環控制二叉樹的總結點/總值for(int j = 1;j <= i;j++) {// 內層循環控制二叉樹的根節點/值dp[i] += dp[j-1] * dp[i-j];}}// 4. 返回return dp[n];}
}

* 動態規劃：01背包理論基礎

https://kamacoder.com/problempage.php?pid=1046

題目描述

小明是一位科學家，他需要參加一場重要的國際科學大會，以展示自己的最新研究成果。他需要帶一些研究材料，但是他的行李箱空間有限。這些研究材料包括實驗設備、文獻資料和實驗樣本等等，它們各自占據不同的空間，并且具有不同的價值。

小明的行李空間為 N，問小明應該如何抉擇，才能攜帶最大價值的研究材料，每種研究材料只能選擇一次，并且只有選與不選兩種選擇，不能進行切割。

輸入描述

第一行包含兩個正整數，第一個整數 M 代表研究材料的種類，第二個正整數 N，代表小明的行李空間。

第二行包含 M 個正整數，代表每種研究材料的所占空間。

第三行包含 M 個正整數，代表每種研究材料的價值。

輸出描述

輸出一個整數，代表小明能夠攜帶的研究材料的最大價值。

輸入示例

6 1
2 2 3 1 5 2
2 3 1 5 4 3

輸出示例

提示信息

小明能夠攜帶 6 種研究材料，但是行李空間只有 1，而占用空間為 1 的研究材料價值為 5，所以最終答案輸出 5。

數據范圍：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空間和價值都小于等于 1000

思路: 動態規劃

確定dp數組以及下標的含義
- 因為有兩個維度需要分別表示：物品和背包容量dp[i] [j], i 來表示物品、j表示背包容量。
確定遞推公式

遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

- **不放物品i**：背包容量為j，里面不放物品i的最大價值是dp[i - 1] [j]。
- **放物品i**：背包空出物品i的容量后，背包容量為j - weight[i]，dp[i - 1] [j - weight[i]] 為背包容量為j - weight[i]且不放物品i的最大價值，那么dp[i - 1] [j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值

dp數組如何初始化
- i 是由 i-1 推導出來，那么i為0的時候就一定要初始化。
- dp[0] [j]，即：i為0，存放編號0的物品的時候，各個容量的背包所能存放的最大價值。
- 那么很明顯當 j < weight[0]的時候，dp[0] [j] 應該是 0，因為背包容量比編號0的物品重量還小。當j >= weight[0]時，dp[0] [j] 應該是value[0]，因為背包容量放足夠放編號0物品
確定遍歷順序

for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}
}

- 首先一定是遍歷節點數，從遞歸公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，節點數為i的狀態是依靠 i之前節點數的狀態。那么遍歷i里面每一個數作為頭結點的狀態，用j來遍歷。
- 代碼如下：

舉例推導dp數組

代碼:

二維數組

import java.util.Scanner;public class Main{public static void main(String[] args) {// 1. 輸入Scanner sc = new Scanner(System.in);int n = sc.nextInt();int bagweight = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0;i < n;i++) weight[i] = sc.nextInt();for(int i = 0;i < n;i++) value[i] = sc.nextInt();// 2. 創建dp數組. 標號0-(n-1)的材料, 0-bagweight的最大可裝重量int[][] dp = new int[n][bagweight+1];// 3. 初始化, 第一行, 標號為0的材料對bagweight, 只有可裝>=bagweight才能初始化為0材料的價值for(int i = weight[0];i <= bagweight;i++) dp[0][i] = value[0];// 4. 根據公式填充dp數組for(int i = 1;i < n;i++) {// 從1號材料開始遍歷到n-1號for(int j = 0;j <= bagweight;j++) {// 遍歷每一種允許的weightif(j < weight[i]) {// 當前可裝weight不能放入i號材料dp[i][j] = dp[i-1][j];// 與裝到i-1號材料不超過j重量的值一致}else {// 當前可裝i號材料, 則在裝和不裝中選擇一個value最大的dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);}}}// 5. 打印System.out.print(dp[n-1][bagweight]);}
}

一維數組

import java.util.Scanner;
public class Main{public static void main(String[] args) {// 1. 輸入數據Scanner sc = new Scanner(System.in);int N = sc.nextInt();// 總材料種類int bagweight = sc.nextInt();// 行李箱空間(能裝材料最大值)int[] costs = new int[N];// 材料所占空間int[] values = new int[N];// 材料價值// 2. 初始化for(int i = 0;i < N;i++) costs[i] = sc.nextInt();for(int i = 0;i < N;i++) values[i] = sc.nextInt();// 3. 創建dp數組, 保存0-bagweight行李箱所能裝的材料價值int[] dp = new int[bagweight+1];// 4. 根據遞推公式遍歷for(int i = 0;i < N;i++) {// 遍歷每種材料(二維數組每行)for(int j = bagweight;j >= costs[i];j--) {// 行李箱每種大小(倒序, 防止后面的值被前面已經改變的值影響)dp[j] = Math.max(dp[j],dp[j-costs[i]] + values[i]);}}// 5. 輸出System.out.print(dp[bagweight]);sc.close();}
}

倒序遍歷是為了保證物品i只被放入一次！。但如果一旦正序遍歷了，那么物品0就會被重復加入多次！

舉一個例子：物品0的重量weight[0] = 1，價值value[0] = 15

如果正序遍歷

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此時dp[2]就已經是30了，意味著物品0，被放入了兩次，所以不能正序遍歷。

為什么倒序遍歷，就可以保證物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp數組已經都初始化為0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以從后往前循環，每次取得狀態不會和之前取得狀態重合，這樣每種物品就只取一次了。

那么問題又來了，為什么二維dp數組遍歷的時候不用倒序呢？

因為對于二維dp，dp[i][j]都是通過上一層即dp[i - 1][j]計算而來，本層的dp[i][j]并不會被覆蓋！

416.分割等和子集

416. 分割等和子集

給你一個 只包含正整數 的非空數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

思路: 看作01背包問題, nums[i]對應的數值既是重量也是價值, 背包大小為sum/2, 即平分總重量.

代碼:

class Solution {public boolean canPartition(int[] nums) {// nums[i]代表物品i的開銷和價值// 1. 轉化nums數組, 取動態規劃所需要的數值int n = nums.length;// 物品的種類int sum = 0;// 所有物品價值和for(int i : nums) sum+=i;// 2. 特殊判斷if(sum % 2 != 0) return false;// 3. 初始化int target = sum/2;// 背包大小(要裝入的價值)int[] dp = new int[target+1];// 每個背包大小所能裝入的價值// 4. 根據迭代公式進行遍歷for(int i = 0;i < n;i++) {// 0-(n-1)種物品for(int j = target;j >= nums[i];j--) {// 背包大小 從target-第i種物品所需的價值 所裝入的價值dp[j] = Math.max(dp[j],dp[j-nums[i]] + nums[i]);}// 5. 返回(剪枝), 每層內循環后判斷是否可以結束if(target == dp[target]) return true;}// 5. 返回return false;}
}

1049.最后一塊石頭的重量 II

1049. 最后一塊石頭的重量 II

有一堆石頭，用整數數組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結果如下：

如果 x == y，那么兩塊石頭都會被完全粉碎；
如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。

最后，最多只會剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒有石頭剩下，就返回 0。

思路: 轉換為動規01背包問題, 目標背包大小為總大小的一半(此時兩堆重量最接近, 相減差值最小), 看目標大小的背包最多裝多少物品, 用剩下的減去裝入的即為所求.

代碼:

class Solution {public int lastStoneWeightII(int[] stones) {// 1. 計算背包重量target(要達成的第一堆石頭的重量)int sum = 0;for(int n : stones) sum+=n;int target = sum >> 1;// 2. 創建dp數組int[] dp = new int[target+1];// 3. 初始化: 0// 4. 根據遞歸公式循環遍歷for(int i = 0;i < stones.length;i++) {// 外層物品for(int j = target;j >= stones[i];j--) {// 內層背包dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);}}// 5. 返回return sum - 2*dp[target];// 剩下的一堆: sum-dp[target] >= 分出來的一堆: dp[target]}
}

494.目標和 ?

494. 目標和

給你一個非負整數數組 nums 和一個整數 target 。

向數組中的每個整數前添加 '+' 或 '-' ，然后串聯起所有整數，可以構造一個 表達式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串聯起來得到表達式 "+2-1" 。

返回可以通過上述方法構造的、運算結果等于 target 的不同 表達式 的數目。

class Solution {public int findTargetSumWays(int[] nums, int target) {// 1. 計算目標要裝的bagSize// l - r = target, l + r = sum => l = (target + sum) / 2 即bagSizeint sum = 0;for(int n : nums) sum+=n;// 特殊判斷if(Math.abs(target) > sum) return 0;if((target+sum) % 2 == 1) return 0;// 計算bagsizeint bagSize = (target + sum) / 2;// 建立dp數組, 裝滿大小為i的背包共有dp[i]種方法int[] dp = new int[bagSize+1];// 裝滿大小為0的背包共有1種方法dp[0] = 1;for(int i = 0;i < nums.length;i++) {for(int j = bagSize;j >= nums[i];j--) {dp[j]+=dp[j-nums[i]];// 放入當前: dp[2] = dp[1] +(放入當前) }}return dp[bagSize];}
}

474.一和零

474. 一和零

給你一個二進制字符串數組 strs 和兩個整數 m 和 n 。

請你找出并返回 strs 的最大子集的長度，該子集中最多有 m 個 0 和 n 個 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

思路: 二維重量的0-1背包問題

確定dp數組（dp table）以及下標的含義dp[i] [j]：最多有i個0和j個1的strs的最大子集的大小為dp[i] [j]。
確定遞推公式dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
dp數組如何初始化01背包的dp數組初始化為0就可以。因為物品價值不會是負數，初始為0，保證遞推的時候dp[i][j]不會被初始值覆蓋。
確定遍歷順序01背包一定是: 外層for循環遍歷物品，內層for循環遍歷背包容量, 且從后向前遍歷

代碼:

class Solution {public int findMaxForm(String[] strs, int m, int n) {// 1. 建立dp數組,i:裝入0的背包大小為i,j:裝入1的背包大小為j,dp[i][j]這么大的背包裝入字符串的個數int[][] dp = new int[m+1][n+1];// 2. 初始化. dp[0][0] = 0, 其余初始化為0(個數最小值), 防止Math.max被影響// 3. 根據迭代公式進行遍歷// 3.1 外層遍歷物品for(String str : strs) {// 統計每個字符串0 1個數, 即兩維度要裝入背包的物品大小 int zero = 0, one = 0;for(char c : str.toCharArray()) {if('0' == c) zero++;else one++;}// 3.2 內層遍歷背包for(int i = m;i >= zero;i--) {// 外層維度遍歷該字符串0的重量for(int j = n;j >= one;j--) {// 內層維度遍歷該字符串1的重量dp[i][j] = Math.max(dp[i][j],dp[i-zero][j-one] + 1);//                不加改字符串 加該字符串}}}// 4. 返回return dp[m][n];}
}

* 完全背包理論基礎-二維DP數組

理論講解: https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85

完全背包和01背包問題唯一不同的地方就是，每種物品有無限件。

52.攜帶研究材料（第七期模擬筆試）

思路:

確定dp數組以及下標的含義dp[i] [j] 表示從下標為[0-i]的物品，每個物品可以取無限次，放進容量為j的背包，價值總和最大是多少。
確定遞推公式dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
- 不放物品i：背包容量為j，里面不放物品i的最大價值是dp[i - 1] [j]。
- 放物品i：背包空出物品i的容量后，背包容量為j - weight[i]，dp[i] [j - weight[i]] 為背包容量為j - weight[i]且不放物品i的最大價值，那么dp[i] [j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值
dp數組如何初始化狀態轉移方程可以看出有一個方向 i 是由 i-1 推導出來，那么i為0的時候就一定要初始化。
- 那么很明顯當 j < weight[0]的時候，dp[0] [j] 應該是 0，因為背包容量比編號0的物品重量還小。
- 當j >= weight[0]時，dp[0] [j] 如果能放下weight[0]的話，就一直裝，每一種物品有無限個。
- 其他下標初始為什么數值都可以，因為都會被覆蓋。但只不過一開始就統一把dp數組統一初始為0，更方便一些。

// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) {dp[0][j] = dp[0][j - weight[0]] + value[0]; 
}

確定遍歷順序先物品后背包或先背包后物品均可.兩種遍歷順序，對于二維dp數組來說，遞推公式所需要的值，二維dp數組里對應的位置都有。
舉例推導dp數組

代碼:

import java.util.Scanner;public class Main {public static void main(String[] args) {// 輸入Scanner sc = new Scanner(System.in);int n = sc.nextInt();int bagweight = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0;i < n;i++) {weight[i] = sc.nextInt();value[i] = sc.nextInt();}// 1. 創建dp數組,dp[i][j]:重量為j的背包放入物品0-i的最大價值int[][] dp = new int[n][bagweight+1];// 2. 初始化for(int j = weight[0];j <= bagweight;j++) {dp[0][j] = dp[0][j-weight[0]] + value[0];// 放入0號物品}// 3. 根據遞推公式遍歷填充for(int i = 1;i < n;i++) {// 外層:遍歷物品1-ifor(int j = 0;j <= bagweight;j++) {// 內層:遍歷背包if(j < weight[i]) {// 當前背包大小不能裝下當前物品dp[i][j] = dp[i-1][j];// 不放入當前物品}else {// 當前背包大小能裝下當前物品dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i]] + value[i]);// 取放入和不放入的最大值}}}// 輸出System.out.print(dp[n-1][bagweight]);sc.close();}
}

518.零錢兌換 II

518. 零錢兌換 II

給你一個整數數組 coins 表示不同面額的硬幣，另給一個整數 amount 表示總金額。

請你計算并返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回 0 。

假設每一種面額的硬幣有無限個。

題目數據保證結果符合 32 位帶符號整數。

**思路: ** 完全背包問題.

確定dp數組以及下標的含義

 dp[j]：湊成總金額j的貨幣組合數為dp[j]

確定遞推公式

 本題 二維dp 遞推公式： `dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]`壓縮成一維：`dp[j] += dp[j - coins[i]]`

dp數組如何初始化

 裝滿背包容量為0 的方法是1，即不放任何物品，`dp[0] = 1`

確定遍歷順序外物品內背包: 組合數外背包內物品: 排列數

 純完全背包求得裝滿背包的最大價值是多少，和湊成總和的元素有沒有順序沒關系，即：有順序也行，沒有順序也行, 而本題要求湊成總和的組合數，元素之間明確要求<font style="background-color:#f3bb2f;">沒有順序</font>。本題是求湊出來的方案個數，且每個方案個數是<font style="background-color:#f3bb2f;">組合數</font>。

舉例推導dp數組

代碼:

class Solution {public int change(int amount, int[] coins) {// 1. 建立dp數組.dp[i]:大小為i的背包 用coins中的硬幣湊成amount(背包總重量) 有dp[i]種組合方法int[] dp = new int[amount+1];// 2. 初始化dp[0] = 1;// 3. 根據遞推公式遍歷for(int i = 0;i < coins.length;i++) {// 外物品:固定物品的出現順序, 確保最后統計的是組合數而不是排列數for(int j = coins[i];j <= amount;j++) {// 內背包:累加不同組合dp[j] += dp[j-coins[i]];}}// 4. 返回return dp[amount];}
}

377.組合總和 Ⅳ

377. 組合總和 Ⅳ

給你一個由不同整數組成的數組 nums ，和一個目標整數 target 。請你從 nums 中找出并返回總和為 target 的元素組合的個數。

題目數據保證答案符合 32 位整數范圍。

**思路: ** 完全背包全排列

代碼:

class Solution {public int combinationSum4(int[] nums, int target) {// 1. 建立dpint[] dp = new int[target+1];// 2. 初始化dp[0] = 1;// 3. 根據遞推公式迭代for(int i = 0;i <= target;i++) {// 背包(0-target)for(int j = 0;j < nums.length;j++) {// 物品(整個nums)if(i >= nums[j]) dp[i] += dp[i-nums[j]];// 背包夠裝}}  // 4. 返回return dp[target];}
}

70. 爬樓梯（進階版）

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬至多m (1 <= m < n)個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

輸入描述：輸入共一行，包含兩個正整數，分別表示n, m

輸出描述：輸出一個整數，表示爬到樓頂的方法數。

輸入示例：3 2

輸出示例：3

提示：

當 m = 2，n = 3 時，n = 3 這表示一共有三個臺階，m = 2 代表你每次可以爬一個臺階或者兩個臺階。

此時你有三種方法可以爬到樓頂。

1 階 + 1 階 + 1 階段
1 階 + 2 階
2 階 + 1 階

**思路: ** 完全背包全排列問題

代碼:

import java.util.Scanner;
public class Main{public static void main(String[] args) {// 1. 輸入Scanner sc = new Scanner(System.in);int n = sc.nextInt();// 背包int m = sc.nextInt();// 物品// 2. 建立dp數組int[] dp = new int[n+1];// 3. 初始化: 為了后序累加, 必須為1不為0dp[0] = 1;// 4. 根據迭代公式遍歷for(int i = 1;i <= n;i++) {// 外背包for(int j = 1;j <= m;j++) {// 內物品(樓梯每次1-m個)if(i >= j) dp[i] += dp[i-j];}}System.out.print(dp[n]);sc.close();}
}

322.零錢兌換

322. 零錢兌換

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

計算并返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

**思路: ** 完全背包(組合數)

代碼:

class Solution {public int coinChange(int[] coins, int amount) {// 1. 建立dp數組int[] dp = new int[amount+1];// 2. 初始化int max = Integer.MAX_VALUE;Arrays.fill(dp,max);// 最大值(防止影響取min)dp[0] = 0;// 總金額為0共0種// 3. 根據遞推公式進行遍歷for(int i = 0;i < coins.length;i++) {// 物品for(int j = coins[i];j <= amount;j++) {// 背包if(dp[j-coins[i]] != max) dp[j] = Math.min(dp[j-coins[i]] + 1,dp[j]);}}// 4. 返回return dp[amount] == max ? -1 : dp[amount];}
}

279.完全平方數

279. 完全平方數

給你一個整數 n ，返回 和為 n 的完全平方數的最少數量 。

完全平方數 是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。

思路: 完全背包, 求種類最小數值.

代碼:

class Solution {public int numSquares(int n) {// 1. 建立dp數組int[] dp = new int[n+1];// 2. 初始化for(int i = 0;i <= n;i++) {dp[i] = Integer.MAX_VALUE;}dp[0] = 0;// 3. 根據遞推公式迭代for(int i = 1;i <= n;i++) {// 外物品for(int j = i*i;j <= n;j++) {// 內背包(完全平方數dp[i] == i*i) dp[j] = Math.min(dp[j],dp[j-i*i] + 1);// 因為有1, 所以每個背包一定有解, 不需要是否為max的判斷來避免加一溢出}}// 4. 返回return dp[n];}
}

139.單詞拆分

139. 單詞拆分

給你一個字符串 s 和一個字符串列表 wordDict 作為字典。如果可以利用字典中出現的一個或多個單詞拼接出 s 則返回 true。

**注意：**不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用。

**思路: ** 完全背包, 排列數, 是否可以

代碼:

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 1. 建立dp數組, dp[i]:長度為i的字符串是否能由wordDict組成boolean[] dp = new boolean[s.length()+1];// 2. 初始化, 為了后序遍歷不全為false, 與dp[0]有關dp[0] = true;// 3. 根據迭代公式循環遍歷(題目要求與順序有關,因此外背包,內物品)Set<String> set = new HashSet<>(wordDict);// 去重收集, 提高效率for(int i = 1;i <= s.length();i++) {for(int j = 0;j < i && !dp[i];j++) {// 當出現dp[i] == true就不需要向后遍歷, 后序不會再改變該值if(set.contains(s.substring(j,i)) && dp[j]) dp[i] = true;// 必須在dp[j] == true的時候才能保證dp[i] == true;}}// 4. 返回return dp[s.length()];}
}

* 多重背包

https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html#%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85

攜帶礦石資源（第八期模擬筆試）

https://kamacoder.com/problempage.php?pid=1066

思路: 完全背包. 把每種商品遍歷的個數放在01背包里面在遍歷一遍

代碼:

import java.util.Scanner;
public class Main {public static void main(String[] args) {// 1. 輸入Scanner sc = new Scanner(System.in);int bagweight = sc.nextInt();int n = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];int[] num = new int[n];for(int i = 0;i < n;i++) weight[i] = sc.nextInt();for(int i = 0;i < n;i++) value[i] = sc.nextInt();for(int i = 0;i < n;i++) num[i] = sc.nextInt();// 2. 創建dp數組int[] dp = new int[bagweight+1];// 總價值for(int i = 0;i < n;i++) {// 物品for(int j = bagweight;j >= weight[i];j--) {// 背包for(int k = 1;k <= num[i] && j >= k*weight[i];k++) {// 物品個數dp[j] = Math.max(dp[j],dp[j-k*weight[i]] + k*value[i]);}}}// 3. 打印System.out.print(dp[bagweight]);}
}

背包問題總結

1. 幾種常見背包

2. 動規解題五部曲

確定dp數組（dp table）以及下標的含義
確定遞推公式
dp數組如何初始化
確定遍歷順序
舉例推導dp數組

3. 背包遞推公式

問能否能裝滿背包（或者最多裝多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，對應題目如下：

動態規劃：416.分割等和子集(opens new window)
動態規劃：1049.最后一塊石頭的重量 II(opens new window)

問裝滿背包有幾種方法：dp[j] += dp[j - nums[i]] ，對應題目如下：

動態規劃：494.目標和(opens new window)
動態規劃：518. 零錢兌換 II(opens new window)
動態規劃：377.組合總和Ⅳ(opens new window)
動態規劃：70. 爬樓梯進階版（完全背包）(opens new window)

問背包裝滿最大價值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，對應題目如下：

動態規劃：474.一和零(opens new window)

問裝滿背包所有物品的最小個數：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，對應題目如下：

動態規劃：322.零錢兌換(opens new window)
動態規劃：279.完全平方數

4. 遍歷順序

01背包

在動態規劃：關于01背包問題，你該了解這些！ (opens new window)中我們講解二維dp數組01背包先遍歷物品還是先遍歷背包都是可以的，且第二層for循環是從小到大遍歷。

和動態規劃：關于01背包問題，你該了解這些！（滾動數組） (opens new window)中，我們講解一維dp數組01背包只能先遍歷物品再遍歷背包容量，且第二層for循環是從大到小遍歷。

#完全背包

在動態規劃：關于完全背包，你該了解這些！ (opens new window)中，講解了純完全背包的一維dp數組實現，先遍歷物品還是先遍歷背包都是可以的，且第二層for循環是從小到大遍歷。

但是僅僅是純完全背包的遍歷順序是這樣的，題目稍有變化，兩個for循環的先后順序就不一樣了。

如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。

如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。

相關題目如下：

求組合數：動態規劃：518.零錢兌換II(opens new window)
求排列數：動態規劃：377. 組合總和 Ⅳ (opens new window)、動態規劃：70. 爬樓梯進階版（完全背包）(opens new window)

如果求最小數，那么兩層for循環的先后順序就無所謂了，相關題目如下：

求最小數：動態規劃：322. 零錢兌換 (opens new window)、動態規劃：279.完全平方數(opens new window)

198.打家劫舍

198. 打家劫舍

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。

思路: 動態規劃.

代碼:

class Solution {public int rob(int[] nums) {// 0. 特殊判斷, 防止dp[1]取值時nums[1]下標越界if(nums.length == 1) return nums[0];// 1. 建立dp數組int[] dp = new int[nums.length];// dp[i]:考慮到nums[i]所偷竊的最大金額// 2. 初始化dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);// 3. 根據遞推公式迭代遍歷for(int i = 2;i < nums.length;i++) {dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);//           不加nums[i]  加nums[i]}// 4. 返回return dp[nums.length-1];}
}

213.打家劫舍 II

213. 打家劫舍 II

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

思路: 動態規劃. 根據打家劫舍I, 將循環拆成兩個順序數組, 分別傳入打家劫舍I的代碼中, 取最大值.

![](https://gitee.com/kiddkid/images/raw/master/202503112155552.jpeg)![](https://gitee.com/kiddkid/images/raw/master/202503112155315.jpeg)

代碼:

class Solution {public int rob(int[] nums) {// 1. 特殊判斷, 保證nums.length >= 2, 使下方傳入doRob的參數合法if(nums.length == 1) return nums[0];// 2. 返回 0 ~ nums.length - 2, 1 ~ nums.length - 1 數組順序遍歷無循環情況下的最大價值return Math.max( doRob(nums,0,nums.length - 2), doRob(nums,1,nums.length - 1) );}// 真正執行打家劫舍的算法, 順序打家劫舍public int doRob(int[] nums,int start,int end) {// 1. 創建dp數組int[] dp = new int[end - start + 1];// 2. 初始化dp[0] = nums[start];// 防止start == end, start+1 > end, 操作范圍內下標越界if(start + 1 <= end) dp[1] = Math.max(nums[start],nums[start + 1]);// 3. 根據遞推公式迭代遍歷for(int i = start + 2;i <= end;i++) {// 以start為對照點計算dp數組的下標, 確保dp數組從0開始順序填充dp[i - start] = Math.max(dp[i - start - 1], dp[i - start - 2] + nums[i]);}// 4. 返回return dp[end - start];}
}

337.打家劫舍 III

337. 打家劫舍 III

小偷又發現了一個新的可行竊的地區。這個地區只有一個入口，我們稱之為 root 。

除了 root 之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。如果 兩個直接相連的房子在同一天晚上被打劫 ，房屋將自動報警。

給定二叉樹的 root 。返回 在不觸動警報的情況下_ ，小偷能夠盜取的最高金額_ 。

**思路: ** 樹形dp

1. 確定遞歸函數的參數和返回值

這里我們要求一個節點偷與不偷的兩個狀態所得到的金錢，那么返回值就是一個長度為2的數組。

參數為當前節點，代碼如下：

int[] doRob(TreeNode* cur) { ... }

其實這里的返回數組就是dp數組。

所以dp數組（dp table）以及下標的含義：下標為0記錄不偷該節點所得到的的最大金錢，下標為1記錄偷該節點所得到的的最大金錢。

2. 確定終止條件

在遍歷的過程中，如果遇到空節點的話，很明顯，無論偷還是不偷都是0，所以就返回

if (cur == NULL) return int[] {0, 0};

這也相當于dp數組的初始化

3. 確定遍歷順序

使用后序遍歷。因為要通過遞歸函數的返回值來做下一步計算。

通過遞歸左節點，得到左節點偷與不偷的金錢。

通過遞歸右節點，得到右節點偷與不偷的金錢。

代碼如下：

// 下標0：不偷，下標1：偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右
// 中

4. 確定單層遞歸的邏輯

如果是偷當前節點，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果對下標含義不理解就再回顧一下dp數組的含義）

如果不偷當前節點，那么左右孩子就可以偷，至于到底偷不偷一定是選一個最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后當前節點的狀態就是{val2, val1}; 即：{不偷當前節點得到的最大金錢，偷當前節點得到的最大金錢}

代碼如下：

vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右// 偷cur
int val1 = cur->val + left[0] + right[0];
// 不偷cur
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};

5. 舉例推導dp數組

以示例1為例，dp數組狀態如下：（注意用后序遍歷的方式推導）

最后頭結點就是取下標0 和下標1的最大值就是偷得的最大金錢。

代碼:

class Solution {public int rob(TreeNode root) {int[] res = doRob(root);// 獲取根節點不偷和偷的情況下獲取金額return Math.max(res[0],res[1]);// 返回偷和不偷的最大值}// 開始打家劫舍public int[] doRob(TreeNode root) {// 1. 遞歸出口: 當前為結點為null, 當前節點偷不偷最大值都為0int[] res = new int[2];if(root == null) return res;// 2. 遞歸主要邏輯: 后序遍歷// 2.1 左int[] leftDp = doRob(root.left);// 2.2 右int[] rightDp = doRob(root.right);// 2.3 中// 2.3.1 不偷當前節點: 左偷不偷最大值 + 右偷不偷最大值res[0] = Math.max(leftDp[0],leftDp[1]) + Math.max(rightDp[0],rightDp[1]);// 2.3.2 偷當前節點: 左右均不偷 + 當前節點的價值res[1] = leftDp[0] + rightDp[0] + root.val;// 3. 返回結果: 偷不偷最大值組成的dp數組return res;    }
}

121.買賣股票的最佳時機

121. 買賣股票的最佳時機

給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

思路: 動態規劃

確定dp數組（dp table）以及下標的含義
- dp[i] [0] 表示第i天持有股票所得最多現金
- 注意這里說的是“持有”，“持有”不代表就是當天“買入”！也有可能是昨天就買入了，今天保持持有的狀態
- dp[i] [1] 表示第i天不持有股票所得最多現金

代碼:

class Solution {public int maxProfit(int[] prices) {// 1. 建立dp數組int len = prices.length;int[][] dp = new int[len][2];// 第i天持有/不持有該股票所獲的最大利潤// 2. 初始化dp[0][0] = -prices[0];// 持有:第一天購買dp[0][1] = 0;// 不持有// 3. 根據遞推公式迭代遍歷for(int i = 1;i < len;i++) {dp[i][0] = Math.max(dp[i-1][0], -prices[i]);// 之前就持有 | 當前持有dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);// 之前就不持有 | 當前不持有}// 4. 返回return dp[len-1][1];// 該題一定是不持有 > 持有}
}

122.買賣股票的最佳時機 II

122. 買賣股票的最佳時機 II

給你一個整數數組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候最多只能持有一股股票。你也可以先購買，然后在 同一天 出售。

返回 你能獲得的最大利潤 。

**思路: ** 同121, 注意購入時本金變化, 由于可以多次買賣, 購入時本金不一定為0了

代碼:

class Solution {public int maxProfit(int[] prices) {// 1. 創建dp數組int len = prices.length;int[][] dp = new int[len][2];// 2. 初始化dp[0][0] = -prices[0];// 持有dp[0][1] = 0;// 不持有// 3. 根據遞推公式循環遍歷for(int i = 1;i < len;i++) {// 之前就持有 | 之前不持有, 現在持有, 由于可以買賣多次, 當前不一定是第一次, 故要用dp[i-1][1] - prices[i]dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);// 之前就不持有 | 之前持有, 現在不持有dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);}// 4. 返回return dp[len-1][1];// 不持有 > 持有}
}

123.買賣股票的最佳時機 III

123. 買賣股票的最佳時機 III

給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成兩筆交易。

**注意：**你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

思路: 動規, 定義五種狀態確保統計兩次買入兩次賣出的情況.

代碼:

class Solution {public int maxProfit(int[] prices) {// 1. 建立dp數組int len = prices.length;int[][] dp = new int[len][5];// 定義五種狀態, 0:無操作 1:第一次買入 2:第一次賣出 3:第二次買入 4:第二次賣出// 2. 初始化dp[0][1] = -prices[0];dp[0][3] = -prices[0];// 3. 根據遞推公式進行遍歷for(int i = 1;i < len;i++) {dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);}// 4. 返回return dp[len-1][4];}
}

188.買賣股票的最佳時機 IV

188. 買賣股票的最佳時機 IV

給你一個整數數組 prices 和一個整數 k ，其中 prices[i] 是某支給定的股票在第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。也就是說，你最多可以買 k 次，賣 k 次。

**注意：**你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

思路: 動態規劃. 將狀態根據循環進行抽象.

代碼:

class Solution {public int maxProfit(int k, int[] prices) {// 1. 建立dp數組int len = prices.length;int[][] dp = new int[len][2*k+1];// 0~len,0~2k// 2. 初始化: 只有奇數次賣出的時候初始化為-prices[0], 其余均為0for(int i = 1;i < 2*k;i+=2) dp[0][i] = -prices[0];// 3. 根據遞推公式遍歷for(int i = 1;i < len;i++) {// prices下標ifor(int j = 0;j < 2*k;j+=2) {// 次數遞增, 循環只寫 持有/不持有 兩種狀態dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i]);dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);}}// 4. 返回return dp[len-1][2*k];}
}

309.買賣股票的最佳時機含冷凍期

309. 買賣股票的最佳時機含冷凍期

給定一個整數數組prices，其中第 prices[i] 表示第 *i* 天的股票價格。

設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

**注意：**你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

思路: 動態規劃.

122基礎上定義冷凍期, 定義四種狀態: [持有, 賣出, 冷凍期, 保持賣出 … ]

0: 持有
1: 保持賣出
2: 賣出當天
3: 冷凍期

代碼:

class Solution {public int maxProfit(int[] prices) {// 1. 建立dp數組int len = prices.length;int[][] dp = new int[len][4];// 2. 初始化dp數組dp[0][0] = -prices[0];// 3. 根據遞推公式遍歷for(int i = 1;i < len;i++) {// dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]));dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);dp[i][2] = dp[i][0] + prices[i];dp[i][3] = dp[i-1][2];}// 4. 返回return Math.max(dp[len-1][1], Math.max(dp[len-1][2], dp[len-1][3]));}
}

714.買賣股票的最佳時機含手續費

714. 買賣股票的最佳時機含手續費

給定一個整數數組 prices，其中 prices[i]表示第 i 天的股票價格；整數 fee 代表了交易股票的手續費用。

你可以無限次地完成交易，但是你每筆交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。

返回獲得利潤的最大值。

**注意：**這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續費。

思路: 在買賣股票II的基礎上添加手續費.

代碼:

class Solution {public int maxProfit(int[] prices, int fee) {// 1. dpint n = prices.length;int[][] dp = new int[n][2];// 2. 初始化dp[0][0] = -prices[0];// 3. 遍歷for(int i = 1;i < n;i++) {dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);// 一次交易:買入-持有-賣出, 賣出時支付手續費}// 4. 返回return Math.max(dp[n-1][0], dp[n-1][1]);}
}

300.最長遞增子序列

300. 最長遞增子序列

給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。

子序列 是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

**思路: ** 動規.

dp[i]的定義: dp[i]表示i之前包括i的以nums[i]結尾的最長遞增子序列的長度
狀態轉移方程: 位置i的最長升序子序列等于j從0到i-1各個位置的最長升序子序列 + 1 的最大值。if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);注意這里不是要dp[i] 與 dp[j] + 1進行比較，而是我們要取dp[j] + 1的最大值。
dp[i]的初始化: 每一個i，對應的dp[i]（即最長遞增子序列）起始大小至少都是1.
確定遍歷順序: dp[i] 是有0到i-1各個位置的最長遞增子序列推導而來，那么遍歷i一定是從前向后遍歷。j其實就是遍歷0到i-1，那么是從前到后，還是從后到前遍歷都無所謂，只要吧 0 到 i-1 的元素都遍歷了就行了。所以默認習慣從前向后遍歷。
```
 遍歷i的循環在外層，遍歷j則在內層，代碼如下：
```

for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取長的子序列
}

舉例推導dp數組

輸入：[0,1,0,3,2]，dp數組的變化如下：

代碼:

class Solution {public int lengthOfLIS(int[] nums) {// 1. dp數組int n = nums.length;int[] dp = new int[n];// i之前包括i的以nums[i]結尾的最長遞增子序列的長度// 2. 初始化Arrays.fill(dp,1);// 至少有nums[i], 故初始為1// 3. 根據遞推公式遍歷int res = 1;for(int i = 1;i < n;i++) {// 當前遍歷到的位置for(int j = 0;j < i;j++) {// 0~i, 前面的可以不相鄰if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);}res = Math.max(res, dp[i]);// 找出最大的dp[i]}// 4. 返回return res;}
}

674.最長連續遞增序列

674. 最長連續遞增序列

給定一個未經排序的整數數組，找到最長且 連續遞增的子序列，并返回該序列的長度。

連續遞增的子序列 可以由兩個下標 l 和 r（l < r）確定，如果對于每個 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續遞增子序列。

**思路: ** 動規. 類似300.

代碼:

class Solution {public int findLengthOfLCIS(int[] nums) {// 1. dpint n = nums.length;int[] dp = new int[n];// 2. 初始化Arrays.fill(dp, 1);// 3. 根據遞推公式遍歷int res = 1;for(int i = 1;i < n;i++) {if(nums[i - 1] < nums[i]) {// 注意: 比較的是nums里的數值, 由于連續, 只需要相鄰比較dp[i] = dp[i - 1] + 1;}if(dp[i] > res) res = dp[i];}// 4. 返回return res;}
}

718.最長重復子數組

718. 最長重復子數組

給兩個整數數組 nums1 和 nums2 ，返回 兩個數組中 公共的 、長度最長的子數組的長度 。

**思路: ** 二維dp數組

確定dp數組（dp table）以及下標的含義
- dp[i] [j] ：以下標i - 1為結尾的A，和以下標j - 1為結尾的B，最長重復子數組長度為dp[i] [j]。（特別注意： “以下標i - 1為結尾的A” 標明一定是以A[i-1]為結尾的字符串）
- 其實dp[i] [j]的定義也就決定著，我們在遍歷dp[i][j]的時候i 和 j都要從1開始。
確定遞推公式
- 根據dp[i] [j]的定義，dp[i] [j]的狀態只能由dp[i - 1] [j - 1]推導出來。
- 即當A[i - 1] 和B[j - 1]相等的時候，dp[i] [j] = dp[i - 1] [j - 1] + 1;
- 根據遞推公式可以看出，遍歷i 和 j 要從1開始
dp數組如何初始化
- 根據dp[i] [j]的定義，dp[i] [0] 和dp[0] [j]其實都是沒有意義的
- 但dp[i] [0] 和dp[0] [j]要初始值，因為為了方便遞歸公式dp[i] [j] = dp[i - 1] [j - 1] + 1;
- 所以dp[i] [0] 和dp[0] [j]初始化為0。
確定遍歷順序
- 外層for循環遍歷A，內層for循環遍歷B。(換過來也行)
- 同時題目要求長度最長的子數組的長度。所以在遍歷的時候順便把dp[i] [j]的最大值記錄下來。

for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}
}

舉例推導dp數組

代碼:

class Solution {public int findLength(int[] nums1, int[] nums2) {// 1. 建立dp數組    // dp[i][j]: nums1到i-1, nums2到j-1 兩數組最長重復子數組, dp往后順移一位, 因此長度需要加一int[][] dp = new int[nums1.length + 1][nums2.length + 1];// 2. 初始化:dp[i][0] == 0, dp[0][i] == 0  0-1無意義// 3. 根據遞推公式遍歷int res = 0;for(int i = 1;i <= nums1.length;i++) {// nums1for(int j = 1;j <= nums2.length;j++) {// nums2if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;// 根據nums1[i-1] num2[j-1]更新dpif(dp[i][j] > res) res = dp[i][j];// 統計最大的dp[i][j]}}// 4. 返回return res;}
}

1143.最長公共子序列

1143. 最長公共子序列

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。

一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。

**思路: ** 因為可以不連續, 當兩個字符串當前字符不相等的時候還可以根據之前的結果繼續統計.

dp[i] [j]：長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列為dp[i] [j]

代碼:

class Solution {public int longestCommonSubsequence(String text1, String text2) {// 0. 把字符串轉為字符串數組char[] s1 = text1.toCharArray();char[] s2 = text2.toCharArray();// 1. 創建dp// dp[0][0] ~ dp[s1.length][s2.length]: i~s1.length-1, j~s2.length-1int[][] dp = new int[s1.length + 1][s2.length + 1];// 2. 初始化: dp[0][j], dp[i][0] 均初始化為0// 3. 根據遞推公式遍歷for(int i = 1;i <= s1.length;i++) {// s1for(int j = 1;j <= s2.length;j++) {// s2if(s1[i-1] == s2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;}else {// 當前字符不相等, 不需要+1dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}// 4. 返回return dp[s1.length][s2.length];}
}

1035.不相交的線

1035. 不相交的線

在兩條獨立的水平線上按給定的順序寫下 nums1 和 nums2 中的整數。

現在，可以繪制一些連接兩個數字 nums1[i] 和 nums2[j] 的直線，這些直線需要同時滿足：

nums1[i] == nums2[j]
且繪制的直線不與任何其他連線（非水平線）相交。

請注意，連線即使在端點也不能相交：每個數字只能屬于一條連線。

以這種方法繪制線條，并返回可以繪制的最大連線數。

思路: 不相交的線連接的就是兩個數組例的最長公共子序列, 思路同1143, 代碼同1143.

代碼:

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length + 1][nums2.length + 1];for(int i = 1;i <= nums1.length;i++) {for(int j = 1;j <= nums2.length;j++) {if(nums1[i - 1] == nums2[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[nums1.length][nums2.length];}
}

53.最大子數組和

53. 最大子數組和

給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

子數組是數組中的一個連續部分。

思路: 動態規劃.

確定dp數組（dp table）以及下標的含義

 **dp[i]：包括下標i（以nums[i]為結尾）的最大連續子序列和為dp[i]**。

確定遞推公式

 dp[i]只有兩個方向可以推出來：

dp[i - 1] + nums[i]，即：nums[i]加入當前連續子序列和
nums[i]，即：從頭開始計算當前連續子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

dp數組如何初始化

從遞推公式可以看出來dp[i]是依賴于dp[i - 1]的狀態，dp[0]就是遞推公式的基礎。

根據dp[i]的定義，很明顯dp[0]應為nums[0]即dp[0] = nums[0]。

確定遍歷順序

遞推公式中dp[i]依賴于dp[i - 1]的狀態，需要從前向后遍歷。

舉例推導dp數組

代碼:

class Solution {public int maxSubArray(int[] nums) {// 1. 創建dp數組, dp[i]: 統計到nums[i]的最大子數組和 int[] dp = new int[nums.length];// 2. 初始化dp[0] = nums[0];// 3. 根據遞推公式遍歷int res = dp[0];for(int i = 1;i < nums.length;i++) {// 跟前面連接 | 從nums[i]開始dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);// 統計dp[i]的最大值作為返回值if(dp[i] > res) res = dp[i];}// 4. 返回return res;}
}

392.判斷子序列

392. 判斷子序列

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

思路: 動態規劃.

確定dp數組（dp table）以及下標的含義

 **dp[i] [j] 表示以下標i-1為結尾的字符串s，和以下標j-1為結尾的字符串t，相同子序列的長度為dp[i] [j]**。注意這里是判斷s是否為t的子序列。即t的長度是大于等于s的。

確定遞推公式

if (s[i - 1] == t[j - 1])，那么dp[i] [j] = dp[i - 1] [j - 1] + 1;，因為找到了一個相同的字符，相同子序列長度自然要在dp[i-1] [j-1]的基礎上加1
if (s[i - 1] != t[j - 1])，此時相當于t要刪除元素，t如果把當前元素t[j - 1]刪除，那么dp[i] [j] 的數值就是看s[i - 1]與 t[j - 2]的比較結果了，即：dp[i] [j] = dp[i] [j - 1];

其實這里大家可以發現和 1143.最長公共子序列 (opens new window)的遞推公式基本那就是一樣的，區別就是本題如果刪元素一定是字符串t，而 1143.最長公共子序列是兩個字符串都可以刪元素。

dp數組如何初始化

dp[i] [j]是依賴于dp[i - 1] [j - 1] 和 dp[i] [j - 1]，所以dp[0] [0]和dp[i] [0]是一定要初始化的。

確定遍歷順序

同理從遞推公式可以看出dp[i] [j]都是依賴于dp[i - 1] [j - 1] 和 dp[i] [j - 1]，那么遍歷順序也應該是從上到下，從左到右

如圖所示：

舉例推導dp數組

以示例一為例，輸入：s = “abc”, t = “ahbgdc”，dp狀態轉移圖如下：

dp[i] [j]表示以下標i-1為結尾的字符串s和以下標j-1為結尾的字符串t 相同子序列的長度，所以如果dp[s.size()] [t.size()] 與字符串s的長度相同說明：s與t的最長相同子序列就是s，那么s 就是 t 的子序列。

圖中dp[s.size()] [t.size()] = 3，而s.size() 也為3。所以s是t 的子序列，返回true。

代碼:

class Solution {public boolean isSubsequence(String s, String t) {int len1 = s.length(), len2 = t.length();// 1. 建立dp數組: dp[i][j] = 統計到s[i-1], t[j-1], t[j-1]所含s[i-1]的子序列int[][] dp = new int[len1 + 1][len2 + 1];// 2. 根據遞推公式遍歷for(int i = 1;i <= len1;i++) {for(int j = 1;j <= len2;j++) {if(s.charAt(i - 1) == t.charAt(j - 1)) {// s(i - 1) t(j - 1)dp[i][j] = dp[i - 1][j - 1] + 1;// + 1}else dp[i][j] = dp[i][j - 1];}}// 3. 返回, 看len2與len1公共子序列的長度是否為len2return dp[len1][len2] == len1;}
}

115.不同的子序列

115. 不同的子序列

給你兩個字符串 s 和 t ，統計并返回在 s 的 子序列 中 t 出現的個數，結果需要對 10^9 + 7 取模。

思路: 動規.

確定dp數組（dp table）以及下標的含義

 dp[i] [j]：以i-1為結尾的s子序列中出現以j-1為結尾的t的個數為dp[i][j]。

確定遞推公式

s[i - 1] 與 t[j - 1]相等

s[i - 1] 與 t[j - 1] 不相等

  當s[i - 1] 與 t[j - 1]相等時，dp[i] [j]可以有兩部分組成。一部分是用s[i - 1]來<font style="background-color:#f3bb2f;">匹配</font>，那么個數為dp[i - 1] [j - 1]。即不需要考慮當前s子串和t子串的最后一位字母，所以只需要 dp[i-1] [j-1]。一部分是不用s[i - 1]來匹配，個數為dp[i - 1] [j]。

dp數組如何初始化

 從遞推公式`dp[i][j] = dp[i - 1][j - 1] + dp[i - 1`][j]; 和 `dp[i][j] = dp[i - 1`][j]; 中可以看出dp[i] [j] 是從上方和左上方推導而來，如圖：，那么 dp[i] [0] 和dp[0] [j]是一定要初始化的。

vector<vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1));
for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
for (int j = 1; j <= t.size(); j++) dp[0][j] = 0; // 其實這行代碼可以和dp數組初始化的時候放在一起，但我為了凸顯初始化的邏輯，所以還是加上了。

確定遍歷順序

 從遞推公式`dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1`][j]; 中可以看出dp[i] [j]都是根據左上方和正上方推出來的。所以遍歷的時候一定是從上到下，從左到右，這樣保證dp[i] [j]可以根據之前計算出來的數值進行計算。

代碼如下：

for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++) {if (s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j];}}
}

舉例推導dp數組

代碼:

class Solution {public int numDistinct(String s, String t) {// 1. 建立dp數組int len1 = s.length(), len2 = t.length();int[][] dp = new int[len1 + 1][len2 + 1];// 2. 初始化, 根據遞推公式, 所有值都從左上方, 上方遞推而來, 需要初始化上方(dp[0][j] == 0), 左方// 左:for(int i = 0;i <= len1;i++) {dp[i][0] = 1;}// 3. 根據遞推公式遍歷for(int i = 1;i <= len1;i++) {for(int j = 1;j <= len2;j++) {// 當前位置兩個字符串字符相同if(s.charAt(i - 1) == t.charAt(j - 1)) {// 當前相同: 都去掉i, 之前字符串相同的個數 + 去掉s(i)之前字符串相同的個數dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else {// 當前不同: 值為之前字符串相同的個數dp[i][j] = dp[i - 1][j];}}}// 4. 返回return dp[len1][len2];}
}

583.兩個字符串的刪除操作

583. 兩個字符串的刪除操作

給定兩個單詞 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步數。

每步可以刪除任意一個字符串中的一個字符。

示例 1：

輸入: word1 = "sea", word2 = "eat"
輸出: 2
解釋: 第一步將 "sea" 變為 "ea" ，第二步將 "eat "變為 "ea"

示例 2:

輸入：word1 = "leetcode", word2 = "etco"
輸出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小寫英文字母

**思路: ** 動規, 二維dp數組表示兩個字符串.

代碼:

class Solution {public int minDistance(String word1, String word2) {// 1. dp, dp[i][j]: 以i-1為結尾的字符串word1，和以j-1位結尾的字符串word2，想要達到相等，所需要刪除元素的最少次數。int len1 = word1.length(), len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];// 2. 初始化: for (int i = 0; i <= len1; i++)dp[i][0] = i;// dp[i][0]: 統計到下標為i-1, i: 元素個數為i, 共刪除i次for (int j = 0; j <= len2; j++)dp[0][j] = j;// 3. 根據遞推公式遍歷for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {// 當前字符相同dp[i][j] = dp[i - 1][j - 1];// 跟之前刪除次數相同, 不需要再刪除} else {// 當前字符不相同dp[i][j] = Math.min(dp[i - 1][j - 1] + 2, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));// 考慮到當前位置相同: 在之前已經相同的刪除次數上 刪除 該次需要刪除的個數}}}// 4. 返回return dp[len1][len2];}
}

72.編輯距離

72. 編輯距離

給你兩個單詞 word1 和 word2， 請返回將 word1 轉換成 word2 所使用的最少操作數 。

你可以對一個單詞進行如下三種操作：

插入一個字符
刪除一個字符
替換一個字符

思路:

dp[i][j] : dp[i][j] 表示以下標i-1為結尾的字符串word1，和以下標j-1為結尾的字符串word2，最近編輯距離為dp[i][j]。

代碼:

class Solution {public int minDistance(String word1, String word2) {// 1. 建立dp數組int len1 = word1.length(), len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];// 2. 初始化for(int i = 0;i <= len1;i++) dp[i][0] = i;// 此時兩字符相等其中一個必須全部刪除for(int j = 0;j <= len2;j++) dp[0][j] = j;// 下標到i/j表示統計到i-1, j-1, 一共有i/j個字符// 3. 根據遞推公式遍歷for(int i = 1;i <= len1;i++) {// 0已經初始化for(int j = 1;j <= len2;j++) {// 0已經初始化if(word1.charAt(i - 1) == word2.charAt(j - 1)) {// 當前字符相等dp[i][j] = dp[i - 1][j - 1];// 在上一步操作的基礎上不需要添加任何操作}else {// 當前兩字符不等dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;// 1. dp[i - 1][j - 1]的基礎上修改當前兩個其中一個使其和另一個字符相等// 2. dp[i - 1][j]的基礎上再刪除一個dp[i]// 3. dp[i][j - 1]的基礎上再刪除一個dp[j]}}}// 4. 返回return dp[len1][len2];}
}

647.回文子串

647. 回文子串

給你一個字符串 s ，請你統計并返回這個字符串中 回文子串 的數目。

回文字符串 是正著讀和倒過來讀一樣的字符串。

子字符串 是字符串中的由連續字符組成的一個序列。

思路:

確定dp數組（dp table）以及下標的含義布爾類型的dp[i][j]：表示區間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i][j]為true，否則為false。
確定遞推公式s[i]!=s[j]，dp[i] [j]=false。s[i]==s[j]

if (s[i] == s[j]) {if (j - i <= 1) { // 情況一 和 情況二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情況三result++;dp[i][j] = true;}
}

result就是統計回文子串的數量。

- 情況一：i==j，同一個字符例如a，當然是回文子串
- 情況二：j - i ==1，例如aa，也是回文子串
- 情況三：j - i > 1，例如cabac，此時s[i]與s[j]已經相同了，我們看i到j區間是不是回文子串就看aba是不是回文就可以了，那么aba的區間就是 i+1 與 j-1區間，這個區間是不是回文就看dp[i + 1] [j - 1]是否為true。

dp數組如何初始化dp[i] [j] = false，剛開始不可能全都匹配上。
確定遍歷順序首先從遞推公式中可以看出，情況三是根據dp[i + 1] [j - 1]是否為true，在對dp[i] [j]進行賦值true的。dp[i + 1] [j - 1] 在 dp[i][j]的左下角所以一定要從下到上，從左到右遍歷，這樣保證dp[i + 1][j - 1]都是經過計算的。
舉例推導dp數組

代碼:

class Solution {public int countSubstrings(String s) {// 1. 建立dp數組char[] str = s.toCharArray();int len = str.length;// dp[i][j]: s(i) ~ s(j) 組成的字符串是否為回文子串boolean[][] dp = new boolean[len][len];// 根據dp數組統計最終返回的結果int res = 0;// 2. 初始化: 全部默認初始化為false// 3. 根據遞推公式進行遍歷for(int i = len - 1;i >= 0;i--) {// 外層從下往上for(int j = i;j < len;j++) {// 內層從左往右// 默認初始值為false, 只有當前兩字符相等時才有可能賦值為trueif(str[i] == str[j]) {if(j - i <= 1) {// a | aadp[i][j] = true;res++;}else if(dp[i + 1][j - 1]) {// a xxxxx a, 根據xxxxx進行判斷dp[i][j] = true;res++;}}}}// 4. 返回return res;}
}

516.最長回文子序列

516. 最長回文子序列

給你一個字符串 s ，找出其中最長的回文子序列，并返回該序列的長度。

子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個序列。

示例 1：

輸入：s = "bbbab"
輸出：4
解釋：一個可能的最長回文子序列為 "bbbb" 。

示例 2：

輸入：s = "cbbd"
輸出：2
解釋：一個可能的最長回文子序列為 "bb" 。

提示：

1 <= s.length <= 1000
s 僅由小寫英文字母組成

思路:

確定dp數組（dp table）以及下標的含義

 `dp[i][j]`**：字符串s在[i, j]范圍內最長的回文子序列的長度為**`dp[i][j]`。

確定遞推公式
- 如果s[i]與s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
- 如果s[i]與s[j]不相同，說明s[i]和s[j]的同時加入并不能增加[i,j]區間回文子序列的長度，那么分別加入s[i]、s[j]看看哪一個可以組成最長的回文子序列。
  - 加入s[j]的回文子序列長度為dp[i + 1][j]。
  - 加入s[i]的回文子序列長度為dp[i][j - 1]。
- 那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
dp數組如何初始化從遞推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出遞推公式是計算不到 i 和j相同時候的情況。所以需要手動初始化一下，當i與j相同，那么dp[i][j]一定是等于1的，即：一個字符的回文子序列長度就是1。其他情況dp[i][j]初始為0就行，這樣遞推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不會被初始值覆蓋。
確定遍歷順序從遞歸公式中，可以看出，dp[i][j] 依賴于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]所以遍歷i的時候一定要從下到上遍歷，這樣才能保證下一行的數據是經過計算的。
舉例推導dp數組

代碼:

class Solution {public int longestPalindromeSubseq(String s) {// 1. 創建dp數組, dp[i][j]: s[i] ~ s[j]范圍內的最長回文子序列int len = s.length();int[][] dp = new int[len][len];// 2. 初始化: 遞推公式一直往中間集中, 初始化dp[i][i]只有一個字符, 長度為1的回文字符列for(int i = 0;i < len;i++) dp[i][i] = 1;// 3. 根據遞推公式遍歷for(int i = len - 1;i >= 0;i--) {// 從下往上for(int j = i + 1;j < len;j++) {// 從左往右if(s.charAt(i) == s.charAt(j)) {// 當前字符相等dp[i][j] = dp[i + 1][j - 1] + 2;// i+1 ~ j-1 字符串的最長回文子序列 + 2}else {// 當前字符不等dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);// 分別考慮兩邊的字符的最長回文子序列}}}// 4. 返回return dp[0][len - 1];}
}