【代码随想录】-动态规划专题

理论基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

动态规划问题，将拆解为如下五步曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

动态规划在debug时，找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

斐波拉契数列

作为入门动态规划，讲的很好：代码随想录 (programmercarl.com)

/*** 509. 斐波那契数* @param n* @return*/
public int fib(int n) {if(n == 0) return 0;int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for (int i = 2; i < dp.length; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}

爬楼梯

/*** 70. 爬楼梯* @param n* @return*/
public int climbStairs(int n) {if(n <=2) return n;int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for (int i = 3; i < dp.length; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}

使用最小花费爬楼梯

/*** leetcode-746. 使用最小花费爬楼梯* @param cost* @return*/
public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length + 1];//到达第i台阶所花费的最少体力为dp[i]dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.length; i++) { //数组最后元素的后一个才是要的答案//两种跳法// 1. dp[i - 1] 跳到 dp[i] :  cost[i-1]+dp[i-1]// 2.dp[i - 2] 跳到 dp[i] :cost[i-2]+dp[i-2]dp[i] = Math.min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);}return dp[cost.length];
}

不同路径

/*** 62. 不同路径** @param m* @param n* @return*/public int uniquePaths(int m, int n) { // m是行 n是列int[][] dp = new int[m][n];
//        dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。// dp[i][j] 由上 左两个方向推导而来 dp[i][j] = dp[i-1][j] + dp[i][j-1]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];}}return dp[m-1][n-1];}

不同路径 II

 /*** 63. 不同路径 II* @param obstacleGrid* @return*/public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];
//        dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。// dp[i][j] 由上 左两个方向推导而来 dp[i][j] = dp[i-1][j] + dp[i][j-1]//第一行 第一列肯定是只有一种可能 中间要是有障碍物就过不去了for (int i = 0; i < m&& obstacleGrid[i][0] == 0;  i++) {dp[i][0] = 1;}for (int i = 0; i < n&&obstacleGrid[0][i] == 0; i++) {dp[0][i] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}

整数拆分

/*** leetcode-343. 整数拆分* @param n* @return*/
public int integerBreak(int n) {/*当 n≥2时，可以拆分成至少两个正整数的和。令 k是拆分出的第一个正整数，则剩下的部分是 n−k，n−k 可以不继续拆分，或者继续拆分成至少两个正整数的和*/int[] dp = new int[n+1]; // 拆解数字i，可以得到的最大乘积为dp[i]。dp[1] = 1;dp[2] = 1;for (int i = 3; i <= n; i++) {for (int j = 1; j <= i-1 ; j++) { // j在动态变化 保留最大值dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));}}return dp[n];
}

不同的二叉搜索树

/*** leetcode-96. 不同的二叉搜索树* @param n* @return*/
public int numTrees(int n) {int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];
}

背包问题——理论基础

01背包，和完全背包应对面试，最多可以再来一个多重背包。

背包问题的理论基础重中之重是01背包，一定要理解透！

leetcode上没有纯01背包的问题，都是01背包应用方面的题目。

01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是$o(2^n)$，这里的n表示物品数量。

暴力解法是指数级别的时间复杂度。

举例：

背包的最大容量是4：

物品：

背包能背的物品最大价值是多少？

二维dp数组01背包

1. 确定dp数组以及下标的含义

   二维数组的写法：

   dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

​

​ 横i，竖j

2. 确定递推公式

   j容量下到前i个物品的讨论，有两种情况：

   • 选择不装第i个物品，则退回到i-1行，直接选择dp[i-1][j]作为该情况下最大价值(上)
   • 装第i个物品，由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值(左上, j - weight【i】，这里可以理解为背包需要留出这个物品i的容量才可以放物品i)

   当i放进去时，那么这时候整个物品集就被分成两部分，1到i-1和第i个，而这是i是确定要放进去的，那么就把j空间里的wi给占据了，只剩下j－wi的空间给前面i－1，那么只要这时候前面i－1在j－wi空间里构造出最大价值，即dp【i－1】【j－wi】，再加上此时放入的i的价值vi，就是dpij了

   所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

   这样做的原因主要就在于，表dp[i][j]以前的所有数据都已经代表了价值最大的最佳情况。

   • 装i

     0-1背包问题下每个物品只能放一件，所以用j-i物品的体积=f，查表dp[i-1][f]直接得到，装i时前f空间的最大价值。所以装i的最大价值就等于dp[i][f]+value[i]

   • 不装i

   不装i即需要到前i-1个里面选，也就是前i-1行j背包容量下的最大价值，同理，由于前面都已经是最优解，直接查表dp[i-1][j]就是不装i条件下的最大价值

   因此比较两者价值大小选大者即可再次得到dp[i][j]情况下的最优解

​

代码： 先遍历物品 先遍历背包容量 均可。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

​

……

一维数组（滚动数组）

让数组从二维降到一维，即当前层值和上一层i-1的值共存，当当前层遍历完毕，当前层的所有值都会把一维数组上一层的值全部覆盖掉。（去掉了维度）

为什么要先遍历物品再遍历背包？

本质上二维数组和一维数组差不多，计算某一个值需要使用到上一层的值，在二维数组的图中，先遍历物品可以得出整个i-1层的数据，而先遍历背包每次只有一个i-1层的数据，并且每一层都会把上一个覆盖掉，实际计算中需要的是一整层的数据。

为什么第二层循环（遍历背包容量）要从后往前遍历？

本质上二维数组和一维数组差不多，不过二维数组没有覆盖数据。采用一维数组时，如果先计算前面的（下标前后），在做后面的计算时，需要使用上一层的数据（只会使用下标比自己小的），而前面因为先做计算已经把上一层中后面计算需要使用的数据覆盖掉，无法获取到上一层原来的值，因此不能从前往后遍历。而从后往前遍历，计算下标大的值的时候，下标小的上一层值未被覆盖，可以使用，这样就不会出现需要使用的数据被覆盖掉的问题。

for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

装满背包

**求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];**dp[0] 初始化为1 ，dp[j]其他下标对应的数值应该初始化为0。

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

例如，nums[0] = 1，nums[1] = 5，先遍历物品是先把1加入计算，再把5加入计算，得到的方法数量只会是{1, 5}这种情况。而不会出现{5, 1}的情况。所以先遍历物品求的是组合。

若先遍历背包，背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。所以先遍历背包求的是排列。

分割等和子集

/*** 416. 分割等和子集** @param nums* @return*/
public boolean canPartition(int[] nums) {//类比于01背包 在所给定的数组中挑选出一些数 总和为所有元素总和的一半//nums[i]相当于01背包中的weight[i]//背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值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[] dp = new int[target + 1];for (int i = 0; i < nums.length; i++) {/* for (int j = target; j > 0; j--) {if (j >= nums[i]) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}else{dp[j] = dp[j];}*///简略写法 j < w[i]时候什么都不做即可。换句话说，只需要遍历到j >= w[i]for (int j = target; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[target] == target;
}

最后一块石头的重量 II

/*** leetcode-1049. 最后一块石头的重量 II* @param stones* @return*/
public int lastStoneWeightII(int[] stones) {// 问题可以转化为 把一堆石头分成两堆,求两堆石头重量差最小值// 若要差值最小 则两堆石头的重量要尽量接近所有石头总和的一半//dp[target]里是容量为target的背包所能背的最大重量。//一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]int sum = 0;for (int stone : stones) {sum += stone;}int target = sum / 2;int[] dp = new int[target + 1];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]);}}// target是sum向下取整 sum - dp[target] 一定是大于等于dp[target]return sum - 2*dp[target];
}

目标和

/*** leetcode-494. 目标和** @param nums* @param target* @return*/
public int findTargetSumWays(int[] nums, int target) {// 添加加号的数和为pos 添加减号的数和为neg 元素总和为sum// pos+neg=total pos−neg=target// 进一步：pos=(total+target)/2 neg=(total−target)/2// total和target均已知 此时问题变为在数组中找到和为pos的组合// 题目中的每个1 只能用一次 所以是01背包int sum = 0;for (int num : nums) {sum += num;}if (sum < target) return 0;if ((sum + target) % 2 != 0) return 0; //不整除//dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法int[] dp = new int[target + 1];int pos = (target + sum) / 2;dp[0] = 1; // 填满容量为0的背包有1中方法for (int i = 0; i < nums.length; i++) {for (int j = target; j > nums[i]; j++) {dp[j] += dp[j - nums[j]];}}return dp[pos];
}

一和零

/*** leetcode-474. 一和零** @param strs* @param m* @param n* @return*/
public int findMaxForm(String[] strs, int m, int n) {//字符串数组中的元素看作物品 物品的重量有两个维度// m 和 n相当于是一个背包，两个维度的背包int zeroNum;int oneNum;//dp[i][j]表示i个0和j个1时的最大子集int[][] dp = new int[m + 1][n + 1];for (String str : strs) { // 先遍历物品zeroNum = 0;oneNum = 0;for (char c : str.toCharArray()) {if (c == '0') zeroNum++;else oneNum++;}// 再遍历背包 且倒序for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];
}

完全背包

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件（也就是可以放入背包多次）。

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包 均可
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量for(int i = 0; i < weight.size(); i++) { // 遍历物品if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

从小到大遍历：由于一个物品可以被选择多次，更新dp[j]时，可能因为放入物品i而发生变化。

https://blog.csdn.net/mch2869253130/article/details/81906962

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！

零钱兑换 II

/*** leetcode-518. 零钱兑换 II** @param amount* @param coins* @return*/
public int change(int amount, int[] coins) {//dp[j]：凑成总金额j的货币组合数为dp[j]int[] dp = new int[amount + 1];dp[0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) { //完全背包，正序dp[j] += dp[j - coins[i]];}}return dp[amount];
}

组合总和 Ⅳ

/*** leetcode-377. 组合总和 Ⅳ** @param nums* @param target* @return*/
public int combinationSum4(int[] nums, int target) {//和为j的排列数dp[j]int[] dp = new int[target + 1];dp[0] = 1;//可以取多次，完全背包//dp求排列  先遍历背包容量，for (int i = 1; i <= target; i++) {for (int j = 0; j < nums.length; j++) {if (i >= nums[j]) dp[i] += dp[i - nums[j]];}}return dp[target];
}

爬楼梯(dp)

/*** 70. 爬楼梯** @param n* @return*/
public int climbStairs(int n) {if (n <= 2) return n;int[] dp = new int[n + 1];dp[0] = 1;// 完全背包，求排列数for (int i = 1; i < dp.length; i++) {for (int j = 1; j <= 2; j++) {if (i >= j) dp[i] += dp[i - j];}}return dp[n];
}

零钱兑换

/*** leetcode-322. 零钱兑换** @param coins* @param amount* @return*/
public int coinChange(int[] coins, int amount) {if (amount == 0) return 0;//凑成金额j所需的最少硬币个数dp[j]int[] dp = new int[amount + 1];//求个数 对顺序没有要求 与组合或者是排列没关系int max = Integer.MAX_VALUE;Arrays.fill(dp, max);dp[0] = 0;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {// 只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要if(dp[j-coins[i]] != max){dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] == max ? -1 : dp[amount];
}

完全平方数

/*** leetcode-279. 完全平方数** @param n* @return*/
public int numSquares(int n) {// 完全背包问题//凑成j所需要的完全平方数最小个数dp[j]int[] dp = new int[n + 1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0] = 0; // 若干个平方数中没有0for (int i = 1; i <= n; i++) { // 先背包for (int j = 1; j*j <= i; j++) { // 后物品dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}/* 也可以for (int i = 1; i * i <= n; i++) { // 遍历物品for (int j = i * i; j <= n; j++) { // 遍历背包dp[j] = Math.min(dp[j - i * i] + 1, dp[j]);}}*/return dp[n];
}

背包问题总结

背包递推公式

1. 问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);对应题目：416 1049
2. 问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：494 518 377 70
3. 问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：474
4. 问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：322 279

遍历顺序

01背包中二维dp，物品和背包遍历顺序谁先均可。一维是先物品后背包，且第二层循环是由大到小。

完全背包中一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。仅仅是纯完全背包是上述情况，但是场景不同，会有差别。求组合是先物品后背包，求排列是先背包后物品。

求组合：518

求排列：377

若求最小数，遍历顺序无所谓：322

单词拆分

/*** leetcode-139. 单词拆分* @param s* @param wordDict* @return*/
public boolean wordBreak(String s, List<String> wordDict) {// 一个单词可以使用多次 完全背包问题//字符串长度为i，dp[i]为真，表示可以拆分为一个或多个在字典中出现的单词HashSet<String> set = new HashSet<>(wordDict);boolean[] dp = new boolean[s.length() + 1];dp[0] = true;// 本题相当于求排列 先遍历背包for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i; j++) {if(dp[j] && set.contains(s.substring(j,i-j))){dp[i] = true;break; // 不需要再划分}}}return dp[s.length()];
}

打家劫舍

/*** leetcode-198. 打家劫舍** @param nums* @return*/
public int rob(int[] nums) {if(nums.length == 0) return 0;if(nums.length == 1) return nums[0];// dp[i] 下标为j（包括j）之前可偷的最大金额int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(nums[0],nums[1]);for (int i = 2; i < nums.length; i++) {//不取当前，dp[i-1],取当前dp[i-2]+nums[i]dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.length-1];
}

打家劫舍2

/*** leetcode-213. 打家劫舍 II** @param nums* @return*/
public int rob(int[] nums) {if (nums.length == 0) return 0;if (nums.length == 1) return nums[0];//之前是一排排列 现在是环形 第一个和最后一个只能偷一个// 将其变为两个单排列int res1 = getResult(nums, 1, nums.length - 1);//不偷第一个int res2 = getResult(nums, 0, nums.length - 2);//最后一个不偷if (res1 > res2) return res1;return res2;
}public int getResult(int[] nums, int start, int end) {if(start == end) return nums[start];// dp[j] 下标为j（包括j）之前可偷的最大金额int[] dp = new int[end + 1];dp[start] = nums[start];dp[start + 1] = Math.max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];
}

打家劫舍3

/*** leetcode-337. 打家劫舍 III* @param root* @return*/
public int rob(TreeNode root) {int[] ans = getResult(root);return Math.max(ans[0], ans[1]);
}public int[] getResult(TreeNode root) {if (root == null) return new int[2];int[] left = getResult(root.left); //后序遍历int[] right = getResult(root.right);int[] ans = new int[2];//当前节点不偷 两个孩子拿出最多的钱 孩子偷不偷无所谓ans[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);//当前节点偷，孩子节点就不能偷了//左右孩子选择不偷的钱 加上当前节点的值ans[1] = left[0] + right[0] + root.val;return ans;
}

股票问题

买卖股票的最佳时机

/*** 暴力法，超时* leetocde-121. 买卖股票的最佳时机* @param prices* @return*/
public int maxProfit3(int[] prices) {// 找到最大间距int ans = 0;for (int i = 0; i < prices.length; i++) {for (int j = i; j < prices.length; j++) {ans = Math.max(prices[j]-prices[i],ans);}}return ans;
}/*** 贪心* leetocde-121. 买卖股票的最佳时机* @param prices* @return*/
public int maxProfit2(int[] prices) {//找左最小，右最大int ans = 0;int left = prices[0];for (int i = 0; i < prices.length; i++) {left = Math.min(left,prices[i]);ans = Math.max(ans,prices[i]-left);}return ans;
}/*** 动态规划* leetocde-121. 买卖股票的最佳时机* @param prices* @return*/
public int maxProfit(int[] prices) {if(prices.length < 2) return 0;//dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数//dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数int[][] dp = new int[prices.length][2];dp[0][0] = 0; //不持股就是0dp[0][1] = -prices[0];//开始的现金是0 买入后就是-price[0]for (int i = 1; i < prices.length; i++) {//dp[i][0]，今天不持股// 1. 昨天就不持股，今天保持原状// 2.昨天持股 今天卖出dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);//dp[i][1]，今天持股// 1. 昨天就持股，今天保持原状// 2.昨天不持股 今天买入dp[i][1] = Math.max(dp[i-1][1],-prices[i]);}return dp[prices.length-1][0];
}

买卖股票的最佳时机2

/***leetcode-122. 买卖股票的最佳时机 II* @param prices* @return*/
public int maxProfit(int[] prices) {//dp[i][0] 表示第i天不持有股票所得现金。//dp[i][1] 表示第i天持有股票所得现金。int[][] dp = new int[prices.length][2];dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices.length; i++) {//dp[i][0] 当天不持有股票// 1. 昨天就不持股，今天保持原状// 2.昨天持股 今天卖出dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);//dp[i]s[1]，今天持股// 1. 昨天就持股，今天保持原状// 2.昨天不持股 今天买入dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);}return dp[prices.length-1][0];
}

买卖股票的最佳时机3

/*** leetcode-123. 买卖股票的最佳时机 III** @param prices* @return*/
public int maxProfit(int[] prices) {//本题关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。/*一天一共就有五个状态， 0. 没有操作1第一次持有股票2第一次不持有股票3第二次持有股票4第二次不持有股票*///dp[i][j]表示第i天，j为 [0−4]五个状态，第i天状态j所得最大现金。int[][] dp = new int[prices.length][5];dp[0][0] = 0;//没有操作，就是0dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];//第二次持有依赖于第一次持有，相当于第一次买了又卖再买入dp[0][4] = 0;for (int i = 1; i < prices.length; i++) {dp[i][0] = dp[i - 1][0];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]);}//最后一次卖出的状态是最大的利润return dp[prices.length - 1][4];
}

买卖股票的最佳时机4

/*** leetcode-188. 买卖股票的最佳时机4** @param k* @param prices* @return*/
public int maxProfit(int k, int[] prices) {int len = 2 * k + 1;int[][] dp = new int[prices.length][len];for (int i = 0; i < len; i++) {if (i % 2 != 0) dp[0][i] = -prices[0];}for (int i = 1; i < prices.length; i++) {dp[i][0] = dp[i - 1][0];for (int j = 1; j < len; j++) {if (j % 2 != 0)dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);elsedp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);}}return dp[prices.length - 1][len - 1];
}

最佳买卖股票时机含冷冻期

/*** leetcode-309. 最佳买卖股票时机含冷冻期* @param prices* @return*/
public int maxProfit(int[] prices) {//冷冻期指的是今天卖出股票后下一天不能进行任何操作//关键在于哪一天卖出，在今天买入的时候判断前一天是否卖出过股票//从而不持有股票时 细分为两种状态//0 不持有股票，本来就不持有 并不是因为当天卖出过股票//1 不持有股票 ，因为今天卖出过股票//2 持有股票//第i天状态为j，所剩的最多现金为dp[i][j]。int[][] dp = new int[prices.length][3];dp[0][0] = 0;dp[0][1] = 0;//看作今天买了今天又卖dp[0][2] = -prices[0]; //今天买了股票for (int i = 1; i < prices.length; i++) {// 没有股票，且不是因为我卖出股票而没有// 1 昨天就没股票 2 昨天把股票卖了dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);//没有股票，因为昨天把股票卖了dp[i][1] = dp[i - 1][2] + prices[i];//持股dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] - prices[i]);}return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
}

买卖股票的最佳时机含手续费

/*** leetcode-714. 买卖股票的最佳时机含手续费** @param prices* @param fee* @return*/
public int maxProfit(int[] prices, int fee) {int[][] dp = new int[prices.length - 1][2];dp[0][0] = 0; //不持股dp[0][1] = -prices[0];// 持股for (int i = 1; i < prices.length; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices.length - 1][0];
}

总结

最长递增子序列

/*** leetcode-300. 最长递增子序列** @param nums* @return*/
public int lengthOfLIS(int[] nums) {//dp[i]:以nums[i] 结尾的最长递增子序列长度int[] dp = new int[nums.length];Arrays.fill(dp, 1); //最长递增子序列长度最少是1int ans =1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j])dp[i] = Math.max(dp[i], dp[j] + 1); //取dp[j] + 1的最大值,b}ans = Math.max(dp[i],ans);}//找最大值，并不一定结尾的就最大（例如，结尾的数字最小，就是1，前面的可能更大）return ans;
}

最长连续递增序列

/*** 动态规划* leetcode-674. 最长连续递增序列** @param nums* @return*/
public int findLengthOfLCIS2(int[] nums) {//dp[i]:以nums[i] 结尾的最长连续递增子序列长度int[] dp = new int[nums.length];Arrays.fill(dp, 1); //最长递增子序列长度最少是1int ans = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;}ans = Math.max(ans, dp[i]);}return ans;
}/*** 贪心* leetcode-674. 最长连续递增序列** @param nums* @return*/
public int findLengthOfLCIS(int[] nums) {int ans = 1;int count = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1]) {count++;ans = Math.max(ans, count);} else count = 1;}return ans;
}

最长重复子数组

/*** leetcode-718. 最长重复子数组** @param nums1* @param nums2* @return*/
public int findLength(int[] nums1, int[] nums2) {//以当前下标的前一个下标结尾的最长重复子数组int[][] dp = new int[nums1.length + 1][nums2.length + 1];int ans = 0;for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {if (nums1[i] == nums2[j]) {dp[i + 1][j + 1] = dp[i][j] + 1;}ans = Math.max(ans, dp[i + 1][j + 1]);}}return ans;
}public int findLength(int[] nums1, int[] nums2) {// dp[i][j] 只依赖上一行上一列的对角线的值，所以我们从右上角开始计算。//以当前下标的前一个下标结尾的最长重复子数组int[] dp = new int[nums2.length + 1];int result = 0;for (int i = 1; i <= nums1.length; i++) {for (int j = nums2.length; j > 0; j--) {if (nums1[i - 1] == nums2[j - 1]) {dp[j] = dp[j - 1] + 1;}else {dp[j] = 0;}result = Math.max(result, dp[j]);}}return result;
}

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/solutions/310917/yi-zhang-biao-ba-ju-hua-kan-dong-dong-tai-gui-hua-/

最长公共子序列

/*** leetcode-1143. 最长公共子序列** @param text1* @param text2* @return*/
public int longestCommonSubsequence(String text1, String text2) {int len1 = text1.length();int len2 = text2.length();//表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列//不是i的原因：当i或者j为0时，希望表示的含义是空字符串和另外一个字符串的匹配（相当于往后移动一格）int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {char c1 = text1.charAt(i - 1);for (int j = 1; j <= len2; j++) {char c2 = text2.charAt(j - 1);//两个字符都在lcs中if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;//两个字符至少有一个不在lcs中 需要delse dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}return dp[len1][len2];
}

不相交的线

/*** leetcode-1035. 不相交的线** @param nums1* @param nums2* @return*/
public int maxUncrossedLines(int[] nums1, int[] nums2) {int len = nums1.length;int len2 = nums2.length;int[][] dp = new int[len + 1][len2 + 1];for (int i = 1; i < len + 1; i++) {for (int j = 1; j < len2 + 1; 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[len][len2];
}

最大子数组和

/*** leetcode-53. 最大子数组和** @param nums* @return*/
public int maxSubArray(int[] nums) {//以nums[i]结尾的最大连续子序列和为dp[i]int[] dp = new int[nums.length + 1];int ans = 0;for (int i = 1; i < nums.length; i++) {//两个方向可以推出来//dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和//nums[i]，即：从头开始计算当前连续子序列和(前面的和<=0，丢弃)ans = Math.max(Math.max(dp[i - 1] + nums[i], nums[i]), ans);}return ans;
}

不同的子序列

/*** leetcode-115. 不同的子序列** @param s* @param t* @return*/
public int numDistinct(String s, String t) {int len1 = s.length();int len2 = t.length();//以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 0; i < len1+1; i++) { //t为空串去做匹配dp[i][0] = 1;}for (int i = 1; i < len1 + 1; i++) {char c = s.charAt(i - 1);for (int j = 1; j < len2 + 1; j++) {if (c == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else dp[i][j] = dp[i-1][j];}}return dp[len1][len2];
}

两个字符串的删除操作

/*** leetcode-583. 两个字符串的删除操作** @param word1* @param word2* @return*/
public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i < len1 + 1; i++) {char c = word1.charAt(i - 1);for (int j = 1; j < len2 + 1; j++) {if (c == word2.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 len1 + len2 - 2 * dp[len1][len2];
}public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();// dp数组中存储需要删除的字符个数int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 0; i < len1 + 1; i++) dp[i][0] = i;for (int j = 0; j < len2 + 1; j++) dp[0][j] = j;for (int i = 1; i < len1 + 1; i++) {for (int j = 1; j < len2 + 1; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}else{//dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});//dp[i][j - 1] =dp[i-1][j]= dp[i - 1][j - 1] + 1//->dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2//可以简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}}return dp[len1][len2];
}

编辑距离

/*** leetcode-72. 编辑距离** @param word1* @param word2* @return*/
public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();//dp数组中存储的是最少操作数int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 0; i < len1 + 1; i++) dp[i][0] = i;for (int j = 0; j < len2 + 1; j++) dp[0][j] = j;for (int i = 1; i < len1 + 1; i++) {char c = word1.charAt(i - 1);for (int j = 1; j < len2 + 1; j++) {if (c == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {//word1删除一个元素 dp[i - 1][j]+1//word1添加一个元素 等价于word2删除一个元素即dp[i][j - 1] + 1//例如 word1 = "ad" ，word2 = "a"，word1删除元素'd' 和 word2添加一个元素'd'，// 变成word1="a", word2="ad"， 最终的操作数是一样！//word2替换 dp[i - 1][j - 1] + 1dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;}}}return dp[len1][len2];
}

回文子串

/*** leetcode-647. 回文子串** @param s* @return*/
public int countSubstrings2(String s) {char[] chars = s.toCharArray();int len = chars.length;int ans = 0;// 下标范围(i,j)的字串是否是回文boolean[][] dp = new boolean[len][len];for (int i = len - 1; i >= 0; i--) { //从下到上，从左到右遍历for (int j = i; j < len; j++) {if (chars[i] == chars[j]) {if (i == j || j - i == 1 || dp[i + 1][j - 1]) {ans++;dp[i][j] = true;}}}}return ans;
}/*** 双指针法(中心扩散法)** @param s* @return*/
public int countSubstrings(String s) {char[] chars = s.toCharArray();int len = chars.length;int ans = 0;for (int i = 0; i < len; i++) {ans += getCount(chars, i, i); //单个作为中心点ans += getCount(chars, i, i + 1);//两个作为中心点}return ans;
}public int getCount(char[] chars, int i, int j) {int ans = 0;while (i >= 0 && j < chars.length && chars[i] == chars[j]) {ans++;i--;j++;}return ans;
}

最长回文子序列

/*** leetcode-516. 最长回文子序列** @param s* @return*/
public int longestPalindromeSubseq(String s) {//注意：子序列和字串不同，字串要求连续，而子序列不需要连续char[] chars = s.toCharArray();int len = chars.length;// 下标范围(i,j)的最长的回文子序列的长度int[][] dp = new int[len][len];for (int i = 0; i < len; i++) dp[i][i] = 1; //初始化for (int i = len - 1; i >= 0; i--) { //从下到上for (int j = i + 1; j < len; j++) {if (chars[i] == chars[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} elsedp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}return dp[0][len - 1];
}