阿里云 网站建设,小红书推广方案,南通网站建设搭建,it外包风险文章目录理论基础斐波拉契数列爬楼梯使用最小花费爬楼梯不同路径不同路径 II整数拆分不同的二叉搜索树背包问题——理论基础01背包二维dp数组01背包一维数组#xff08;滚动数组#xff09;装满背包分割等和子集最后一块石头的重量 II目标和一和零完全背包零钱兑换 II组合总和…
文章目录理论基础斐波拉契数列爬楼梯使用最小花费爬楼梯不同路径不同路径 II整数拆分不同的二叉搜索树背包问题——理论基础01背包二维dp数组01背包一维数组滚动数组装满背包分割等和子集最后一块石头的重量 II目标和一和零完全背包零钱兑换 II组合总和 Ⅳ爬楼梯(dp)零钱兑换完全平方数背包问题总结背包递推公式遍历顺序单词拆分打家劫舍打家劫舍2打家劫舍3股票问题买卖股票的最佳时机买卖股票的最佳时机2买卖股票的最佳时机3买卖股票的最佳时机4最佳买卖股票时机含冷冻期买卖股票的最佳时机含手续费总结最长递增子序列最长连续递增序列最长重复子数组最长公共子序列不相交的线最大子数组和不同的子序列两个字符串的删除操作编辑距离回文子串最长回文子序列理论基础
动态规划英文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])。
但如果是贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
动态规划问题将拆解为如下五步曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
动态规划在debug时找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的
斐波拉契数列
作为入门动态规划讲的很好代码随想录 (programmercarl.com)
/*** 509. 斐波那契数* param n* return*/
public int fib(int n) {if(n 0) return 0;int[] dp new int[n1];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 nobstacleGrid[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−kn−k 可以不继续拆分或者继续拆分成至少两个正整数的和*/int[] dp new int[n1]; // 拆解数字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(2n)o(2^n)o(2n)这里的n表示物品数量。
暴力解法是指数级别的时间复杂度。
举例
背包的最大容量是4
物品 背包能背的物品最大价值是多少
二维dp数组01背包 确定dp数组以及下标的含义 二维数组的写法 dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
横i竖j 确定递推公式 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给占据了只剩下jwi的空间给前面i1那么只要这时候前面i1在jwi空间里构造出最大价值即dp【i1】【jwi】再加上此时放入的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] 1nums[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// posnegtotal pos−negtarget// 进一步pos(totaltarget)/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];
}背包问题总结
背包递推公式
问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]);对应题目416 1049问装满背包有几种方法dp[j] dp[j - nums[i]] 对应题目如下494 518 377 70问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]); 对应题目如下474问装满背包所有物品的最小个数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, ListString wordDict) {// 一个单词可以使用多次 完全背包问题//字符串长度为idp[i]为真表示可以拆分为一个或多个在字典中出现的单词HashSetString 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 len11; 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 aword1删除元素d 和 word2添加一个元素d// 变成word1a, word2ad 最终的操作数是一样//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];
}
