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状态，这个状态有可能是之前延续过来的，也有可能是今天才变为这个状态，理解这一点很重要