1.動態規劃總結

1.1 01背

題目描述：假設背包容量為4，物品重量分別為1,3,4，價值分別為10,15,20，使裝入包中的物品的價值最大。

1.1.1 二維數組

先物品后背包，每次新增一個物品，判斷要不要加入到背包中

		/* 先遍歷物品 */for(int i = 1;i < m;i ++){/* 再遍歷背包容量 */for(int j = 1;j <= n;j ++){/* 容量>=當前物品重量，可以考慮放或不放當前物品 */if(j >= nums[i]){dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - nums[i]] + nums[i]);/* 否則只能選擇不放當前物品 */    }else{dp[i][j] = dp[i - 1][j];}}}

先背包后物品

		for(int j = 1;j < n;j ++){for(int i = 1;i <= m;i ++){//判斷當前物品到底加不加入背包if(j >= nums[i]){dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - nums[i]] + nums[i]);}else{dp[i][j] = dp[i - 1][j];}}}

兩種遍歷方式得到的結果相同，不過一個是逐行填寫，一個是逐列填寫。

1.1.2 一維數組

		for(int i = 1;i < m;i ++){for(int j = n;j >= nums[i];j --){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}

一維數組，即滾動數組，先物品后背包，且背包從大到小

如果背包沒有從大到小

		for(int i = 1;i < m;i ++){//背包從小到大for(int j = 1;j <= n;j ++){if(j >= nums[i]){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}}

dp[1]=10,dp[2]=20,此時出現添加入重復物品的情況

如果不是先物品后背包

		for(int j = n;j >= 0;j --){for(int i = 1;i < m;i ++){if(j >= nums[i]){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}}

每次只放入一個物品

對于二維數組，時刻想著可到達當前狀態的路徑（從左上，正上方，正左方）

1.2 完全背包

在求裝滿背包有幾種方案的時候，認清遍歷順序是非常關鍵的。
如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。
如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。

2.斐波那契數(力扣509)

class Solution {public int fib(int n) {if (n < 2){return n;}int f0 = 0, f1 = 1;int res = 0;for (int i = 2; i <= n; i++) {res = f0 + f1;f0 = f1;f1 = res;}return res;}
}

class Solution {/* 遞歸，不過很費時間 */public int fib(int n) {if(n < 2) return n;return fib(n - 1) + fib(n - 2);}
}

3.爬樓梯(力扣70)

//1.動態規劃public int climbStairs(int n) {if(n <= 1) return n;//dp[i]:到達第i階有多少種走法int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for(int i = 3;i <= n;i ++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}//當然此題也可以像斐波那契數列一樣將數組替換為變量

4.使用最小花費爬樓梯(力扣746)

class Solution {public int minCostClimbingStairs(int[] cost) {if(cost == null){return 0;}int len = cost.length;/* dp[i]表示到達第i階的最小花費。特別注意本題有個坑，"樓梯頂部"也算一級，所以動規數組長度為len+1 */int[] dp = new int[len + 1];/* 第一步不花費體力 */dp[0] = 0;dp[1] = 0;for (int i = 2; i <= len; i ++){dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);}return dp[len];}
}

5.不同路徑(力扣62)

//1.動態規劃public int uniquePaths(int m, int n) {//dp[i][j]表示到第i行，第j列的不同路徑總數int[][] dp = new int[m][n];for(int i = 0;i < m;i ++){dp[i][0] = 1;}for(int i = 0;i < n;i ++){dp[0][i] = 1;}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];dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}

/* 可以轉化為組合問題：即從m+n-2個數中取m-1個數，有多少種方法 */public int uniquePaths3(int m, int n) {long ans = 1;for(int i = n,j = 1;j < m;i ++,j ++){ans = ans * i / j;}return (int)ans;}

6.不同路徑 II(力扣63)

class Solution {/* 動態規劃 */public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;/* dp[i][j]:表示到達obstacleGrid[i][j]的可走路徑數量 */int[][] dp = new int[m][n];/* 初始化第一列的值：如果發現1，則后面的行皆初始化為0 */for(int i = 0;i < m;i ++){if(obstacleGrid[i][0] != 1){dp[i][0] = 1;}else{break;}}/* 初始化第一行的值：如果發現1，則后面的列皆初始化為0 */for(int i = 0;i < n;i ++){if(obstacleGrid[0][i] != 1){dp[0][i] = 1;}else{break;}}for(int i = 1;i < m;i ++){for(int j = 1;j < n;j ++){/* 如果數組中對應位置為1，將可達路徑數量置為0 */if(obstacleGrid[i][j] == 1){dp[i][j] = 0;/* 否則，統計從左邊和上邊到達的路徑數量 */    }else{dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
}

7.整數拆分(力扣343)

class Solution {//1.動態規劃public int integerBreak(int n) {/* dp[i]為正整數i拆分結果的最大乘積 */int[] dp = new int[n + 1];/* 初始化 */dp[2] = 1;for(int i = 3; i <= n; i ++){for(int j = 1; j < i; j ++){/* j*(i-j)代表把i拆分為j和i-j兩個數相乘 *//* j*dp[i-j]代表把i拆分成j和繼續把(i-j)這個數拆分，* 取(i-j)拆分結果中的最大乘積與j相乘 */dp[i] = Math.max(dp[i], Math.max(j * (i - j),  j * dp[i - j]));}}return dp[n];}
}

//2.找規律/**       n          拆分*       1           0*       2           1+1*       3           1+2*       4           2+2*       5           3+2*       6           3+3*       7           3+4*       8           3+3+2*       9           3+3+3*       10          3+3+4*       11          3+3+3+2*       ...* *///按3拆分，當剩余數等于1時，和前面的3合并為4，剩余數為2時，直接相乘public int integerBreak2(int n) {if(n <= 3) return n - 1;int a = 1;while(n > 4){n -= 3;a *= 3;}return a * n;}

8.不同的二叉搜索樹(力扣96)

class Solution {//1.動態規劃/** 解題思路：* 假設n個節點存在二叉排序樹的個數是G(n)，1為根節點，2為根節點，...，n為根節點，* 當1為根節點時，其左子樹節點個數為0，右子樹節點個數為n-1，同理當2為根節點時，其左子樹節* 點個數為1，右子樹節點為n-2，所以可得G(n) = G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0)* */public int numTrees(int n) {/* 從1到i分別為頭節點組成的二叉搜索樹的個數為dp[i] */int[] dp = new int[n + 1];dp[0] = 1;/* 分別以1為根節點，以2為根節點...依次類推，統計所有情況 */for(int i = 1;i <= n;i ++){/* 當以i為根節點時，有i-1種情況:分別對應左子樹的數量為0,1...i-1 */for(int j = 0;j < i;j ++){dp[i] += dp[j] * dp[i - j - 1];}}return dp[n];}
}

開始進入動態規劃經典題目：背包問題

9.分割等和子集(力扣416)

做這道題需要做一個等價轉換，即：
是否可以從輸入數組中挑選出一些正整數，使得這些數的和 等于 整個數組元素的和的一半。

// 1、二維數組
class Solution {/* 以可取的數字做為物品，以一半和做為容量，即轉化為01背包問題：*  求背包在給定數字下的最大可裝量，再和目標值作比較*/public boolean canPartition(int[] nums) {if (nums == null || nums.length == 0){return false;}/* 求總和 */int sum = 0;for(int num : nums){sum += num;}/* 總和不能均分為兩份 */if (sum % 2 != 0){return false;}int target = sum / 2;int len = nums.length;/* dp[i][j]代表可裝物品為nums[0]-nums[i](因此dp數組一維長度初始化為len)，* 背包容量為j的情況下，背包內容量的最大價值 */int[][] dp = new int[len][target + 1];for (int j = 0; j <= target; j++) {if (j >= nums[0]){dp[0][j] = nums[0];}}for (int i = 1; i < len; i++) {for (int j = 0; j <= target; j++) {if (j >= nums[i]){dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);} else {dp[i][j] = dp[i - 1][j];}}}/* 判斷最大值是否等于目標值 */return dp[len - 1][target] == target;}
}

畫圖分析
發現此時dp[len - 1][target]剛好為11，返回為true

//2.動態規劃（一維數組）public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int len = nums.length;int sum = 0;for(int i : nums){sum += i;}if(sum % 2 != 0) return false;
//        dp[j]表示 背包總容量是j，最大可以湊成j的子集總和為dp[j]int[] dp = new int[sum / 2 + 1];for(int i = 0;i < len;i ++){for(int j = sum / 2;j >= nums[i];j --){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}return dp[sum / 2] == sum / 2;}

對于2這種一維數組解法

遍歷j的時候要從后往前遍歷，因為從后往前遍歷時，dp[j]的改變不會影響dp[j-nums[i]]；但是如果是從前往后遍歷，dp[j - nums[i]]會影響dp[j]的值，從而出錯

10.最后一塊石頭的重量 II(力扣1049)

此題和力扣416的思路一樣

//1.動態規劃（二維數組）public int lastStoneWeightII(int[] stones) {if(stones == null || stones.length == 0) return 0;int len = stones.length;int sum = 0;for(int i : stones){sum += i;}int target = sum / 2;//dp[i][j]：從stones[0]到stones[i]這些石頭中選擇放入容量為//j的背包中，使得背包容納的石頭的重量最大int[][] dp = new int[len][target + 1];for(int j = 0;j <= target;j ++){if(j >= stones[0]){dp[0][j] = stones[0];}}for(int i = 1;i < len;i ++){for(int j = 0;j <= target;j ++){if(j < stones[i]){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - stones[i]] + stones[i]);}}}return sum - dp[len - 1][target] - dp[len - 1][target];}

//2.動態規劃（一維數組）public int lastStoneWeightII2(int[] stones) {if(stones == null || stones.length == 0) return 0;int len = stones.length;int sum = 0;for(int i : stones){sum += i;}int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0;i < len;i ++){for(int j = target;j >= stones[i];j --){//容量為j的背包所能放下的最大石頭重量dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}

11.目標和(力扣494)

這次和之前遇到的背包問題不一樣了，之前都是求容量為j的背包，最多能裝多少。
本題則是裝滿背包有幾種方法。其實這就是一個組合問題了。
在求裝滿背包有幾種方法的情況下，遞推公式一般為dp[j] += dp[j - nums[i]];

//1.動態規劃（一維數組）public int findTargetSumWays2(int[] nums, int target) {if(nums == null || nums.length == 0) return 0;int len = nums.length;int sum = 0;for(int i : nums){sum += i;}if((sum + target) % 2 == 1) return 0;int size = (target + sum) / 2;if(size < 0) size = -size;//dp[j]:填滿j（包括j）這么大容積的包，有dp[j]種方法int[] dp = new int[size + 1];dp[0] = 1;for(int i = 0;i < len;i ++){for(int j = size;j >= nums[i];j --){dp[j] += dp[j - nums[i]];}}return dp[size];}

12.一和零(力扣474)

//1.動態規劃（三維數組）public int findMaxForm(String[] strs, int m, int n) {if(strs == null || strs.length == 0) return 0;int len = strs.length;//dp[i][m][n]:從strs[0]到strs[i]中選取子集，使得子集中最多有m個0和n個1//的最大子集的長度int[][][] dp = new int[len + 1][m + 1][n + 1];for(int i = 1;i <= len;i ++){int[] cur = caculateOneAndZero(strs[i - 1]);for(int j = 0;j <= m;j ++){for(int k = 0;k <= n;k ++){dp[i][j][k] = dp[i - 1][j][k];int zeros = cur[0];int ones = cur[1];if(j >= zeros && k >= ones){//判斷當前元素要不要放入背包，如果不放入，保持原樣，如果放入，比較原樣和加上當前元素之后哪個子集更長dp[i][j][k] = Math.max(dp[i - 1][j][k],dp[i - 1][j - zeros][k - ones] + 1);}}}}return dp[len][m][n];}public int[] caculateOneAndZero(String s){int[] res = new int[2];for(char c : s.toCharArray()){res[c - '0'] ++;}return res;}

//2.動態規劃（空間優化）public int findMaxForm2(String[] strs, int m, int n) {if(strs == null || strs.length == 0) return 0;int len = strs.length;//dp[m][n]:從strs[0]到strs[i]中選取子集，使得子集中最多有m個0和n個1//的最大子集的長度int[][] dp = new int[m + 1][n + 1];for(int i = 0;i < len;i ++){int[] cur = caculateOneAndZero(strs[i]);int zeros = cur[0];int ones = cur[1];//后兩維都是倒序for(int j = m;j >= zeros;j --){for(int k = n;k >= ones;k --){dp[j][k] = Math.max(dp[j][k],dp[j - zeros][k - ones] + 1);}}}return dp[m][n];}public int[] caculateOneAndZero(String s){int[] res = new int[2];for(char c : s.toCharArray()){res[c - '0'] ++;}return res;}

13.零錢兌換 II(力扣518)

完全背包問題求不同組合的個數：
先遍歷物品，再遍歷背包；

//1.動態規劃（一維數組）public int change(int amount, int[] coins) {if(coins == null || coins.length == 0) return 0;int len = coins.length;//dp[i]：從coins[0]到coins[i]中選取組合，使得總和為amount的不同組合的個數int[] dp = new int[amount + 1];//因為后續dp數組的結果都起于dp[0],所以初始化為1dp[0] = 1;for(int i = 0;i < len;i ++){for(int j = coins[i];j <= amount;j ++){//求個數要累積之前的所有情況dp[j] += dp[j - coins[i]];}}return dp[amount];}

好了，繼續之前的問題，這里的內外循環能換嗎？
顯然不能，因為我們這里定義的子問題是，必須選擇第k個硬幣時，湊成金額i的方案。如果交換了，我們的子問題就變了，那就是對于金額 i, 我們選擇硬幣的方案。

14.組合總和 Ⅳ(力扣377)

完全背包問題求不同排列的個數：
先遍歷背包，再遍歷物品；

//1.動態規劃（完全背包求排列總個數）一維數組public int combinationSum4(int[] nums, int target) {if(nums == null || nums.length == 0) return 0;int len = nums.length;//dp[i]:滿足總合為i的所有組合的個數（題意中表示的是排列的所有情況）int[] dp = new int[target + 1];dp[0] = 1;//排列個數問題，先遍歷背包，再遍歷物品//每一次遍歷，確定了容量，去找物品for(int j = 0;j <= target;j ++){for(int i = 0;i < len;i ++){if(j >= nums[i]){dp[j] += dp[j - nums[i]];}}}return dp[target];}

15.爬樓梯(力扣70)

//1.動態規劃（一維數組）public int climbStairs(int n) {int[] nums = {1,2};//從nums[0]到nums[i]中選取組合，使得總和為n的所有排列的總數目int[] dp = new int[n + 1];dp[0] = 1;for(int j = 0;j <= n;j ++){for(int i = 0;i < nums.length;i ++){if(j >= nums[i]){dp[j] += dp[j - nums[i]];}}}return dp[n];}

//2.動態規劃public int climbStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for(int i = 2;i <= n;i ++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}//當然此題也可以像斐波那契數列一樣將數組替換為變量

16.零錢兌換(力扣322)

1. dp[j] = Math.max(dp[j],dp[j - coins[i]] + 1);
   如果求最大個數，數組初始化為0;使得dp[j]能夠及時更新，防止被dp[j]原來的值覆蓋
   2.如果求最小個數，數組初始化為Integer.MAX_VALUE;原因也是防止被覆蓋

public int coinChange(int[] coins, int amount) {if(coins == null || coins.length == 0) return -1;int len = coins.length;int[] dp = new int[amount + 1];for(int j = 0;j <= amount;j ++){dp[j] = Integer.MAX_VALUE;}dp[0] = 0;for(int i = 0;i < len;i ++){for(int j = coins[i];j <= amount;j ++){if(dp[j - coins[i]] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);}}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}

17.完全平方數(力扣279)

public int numSquares(int n) {int maxIndex = (int)Math.sqrt(n) + 1;int[] weight = new int[maxIndex];for(int i = 1;i <= maxIndex;i ++){weight[i - 1] = i * i;}int[] dp = new int[n + 1];for(int i = 0;i <= n;i ++){dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for(int i = 0;i < weight.length;i ++){for(int j = weight[i];j <= n;j ++){dp[j] = Math.min(dp[j],dp[j - weight[i]] + 1);}}return dp[n];}

18.單詞拆分(力扣139)

//1.動態規劃（一維數組）public boolean wordBreak(String s, List<String> wordDict) {//valid[j]：長度為j的字符串能否由wordDict中的字符串組成boolean[] valid = new boolean[s.length() + 1];//數組初始化為falseArrays.fill(valid,false);//valid[0]初始化為0，其他結果由valid[0]推出valid[0] = true;for(int i = 1;i <= s.length();i ++){for(int j = 0;j < i;j ++){if(wordDict.contains(s.substring(j,i)) && valid[j]){valid[i] = true;}}}return valid[s.length()];}

19.打家劫舍(力扣198)

//1.動態規劃（一維數組）public int rob(int[] nums) {if(nums == null || nums.length == 0) return 0;int len = nums.length;//dp[i]:考慮下標i（包括i）以內的房屋，最多可以偷竊的金額為dp[i]。int[] dp = new int[len + 1];dp[1] = nums[0];for(int i = 2;i <= len;i ++){dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i - 1]);}return dp[len];}

20.打家劫舍 II(力扣213)

//1.動態規劃（一維數組）public int rob(int[] nums) {if(nums == null || nums.length == 0) return 0;if(nums.length == 1) return nums[0];if(nums.length == 2) return Math.max(nums[0],nums[1]);//因為首尾不能同時取，將nums分成兩部分，返回兩部分的最大值中的較大值return Math.max(robRange(nums,0,nums.length - 2),robRange(nums,1,nums.length - 1));}//下面也可以使用變量代替數組進行空間優化public int robRange(int[] nums,int start,int end){int len = end - start + 1;int[] dp = new int[len];dp[0] = nums[start];dp[1] = Math.max(nums[start],nums[start + 1]);for(int i = 2;i < len;i ++){dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i + start]);}return dp[len - 1];}

21.打家劫舍 III(力扣337)

//1.遞歸（超出時間限制）public int rob(TreeNode root) {if(root == null){return 0;}int money = root.val;if(root.left != null){money += (rob(root.left.left) + rob(root.left.right));}if(root.right != null){money += (rob(root.right.left) + rob(root.right.right));}//兩種情況，當前節點取和不取return Math.max(money,rob(root.left) + rob(root.right));}

//2.樹形動態規劃public int rob2(TreeNode root) {int[] ans = robAction(root);//最終取 當前節點取和不取的最大值return Math.max(ans[0],ans[1]);}public int[] robAction(TreeNode root){//res[0]:當前節點不取時獲得的最大金額//res[1]：當前節點取時獲得的最大金額int[] res = new int[2];if(root == null) return res;int[] left = robAction(root.left);int[] right = robAction(root.right);//當前節點不取，最大值 = （左孩子取和不取的最大值） + （右孩子取和不取的最大值）res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);//當前節點取，最大值 = 左孩子不取 + 右孩子不取 + 當前節點的值res[1] = left[0] + right[0] + root.val;return res;}

買賣股票問題總結：共有六個股票相關問題
1.只能買賣一次
2.可以買賣多次
3.最多買賣兩次
4.最多買賣k次
5.買賣多次，賣出有一天冷凍期
6.買賣多次，每次有手續費

做股票問題時一定要注意定義的是第i天處于j狀態，這個狀態有可能是之前延續過來的，也有可能是今天才變為這個狀態，理解這一點很重要