文章目录
一、理论基础二、基础部分T509. 斐波那契数 *T70. 爬楼梯 *T746. 使用最小花费爬楼梯 *T343. 整数拆分 **T96. 不同的二叉搜索树 ***T62. 不同路径 *T63. 不同路径Ⅱ * 三、01背包理论简介T416. 分割等和子集(背包能否装满) **T1049. 最后一块石头的重量Ⅱ(背包最多装多少) ***T494. 目标和(装满背包有多少种方法 有统一公式！) ***T474. 一和零 (两个维度的01背包) ** 四、完全背包理论简介T518. 零钱兑换Ⅱ（装满背包有多少种方式 有统一公式！组合数！遍历顺序）***T377. 组合总和Ⅳ（装满背包有多少种方法 排列数！遍历顺序）***T70. 爬楼梯(装满背包多少种方法,排列数) **T322. 零钱兑换(装满背包最少多少件东西) **T279. 完全平方数(装满背包最少多少件东西) **T139. 单词拆分(能否把背包装满) **** 五、打家劫舍T198. 打家劫舍(相邻) *T213. 打家劫舍Ⅱ(相邻、带环) **T337. 打家劫舍Ⅲ (树形dp,后序遍历) ** 六、股票问题T121. 买卖股票的最佳时机(买卖一次) *T122. 买卖股票的最佳时机Ⅱ(买卖多次) *T123. 买卖股票的最佳时机Ⅲ（2次买入卖出） **T188. 买卖股票的最佳时机Ⅳ(k次买入卖出) **** 前面的题套总结，可以只看此题T309. 最佳买卖股票时机含冷冻期T714. 买卖股票的最佳时机含手续费 七、子序列问题0. 总结1. 不连续子序列T300. 最长上升子序列 **T1143. 最长公共子序列 **T1035. 不相交的线 *** (难在转换题目意思) 2. 连续子序列T674. 最长连续递增序列 *T53. 最大子序和 * (也可以贪心) 3. 编辑距离 (dp含义，递推公式都不好想) ****T392. 判断子序列 **** (是否)T115. 不同的子序列 **** （个数）T583. 两个字符串的删除操作 **** （两个字符串都可操作）T72. 编辑距离 **** 4. 回文T647. 回文子串 ***T516. 最长回文子序列 ***一、理论基础
确定dp数组（dp table）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组二、基础部分
T509. 斐波那契数 *
class Solution {public int fib(int n) {if (n<=1){return n;}int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for (int i=2;i<=n;i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}}
T70. 爬楼梯 *
class Solution {//方法一:斐波那契数组public int climbStairs(int n) {int[] dp = new int[n+2];dp[0]=0;dp[1]=1;dp[2]=2;if(n<=2){return n;}for (int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}}
T746. 使用最小花费爬楼梯 *
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length+1];dp[0]=0;dp[1]=0;for(int i=2;i<=cost.length;i++){dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.length];}}
T343. 整数拆分 **
思路分析推递推公式:
从1遍历j，比较(i - j) * j和dp[i - j] * j 取最大的。递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
那么在取最大值的时候，为什么还要比较dp[i]呢？
因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。代码实现
class Solution {public int integerBreak(int n) {int[] dp = new int[n+1];//dp[i]代表分解数字i最大乘积dp[2]=1;for (int i = 3;i<=n;i++){for(int j = 1;j<=i/2;j++){//把数i 分成j和j-i 如果j-i可以再分 或者j-i不能再分dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}}
T96. 不同的二叉搜索树 ***
思路分析难点1：想到用动态规划
难点2：推递推公式
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量代码实现
class Solution {public int numTrees(int n) {int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for (int i=2;i<=n;i++){for(int j=0;j<i;j++){dp[i] += dp[j]*dp[i-j-1];}}return dp[n];}}
T62. 不同路径 *
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];//记录到每个点的路径总数//初始化for(int i = 0;i<m;i++){dp[i][0]=1;}for(int j = 0;j<n;j++){dp[0][j]=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];}}
T63. 不同路径Ⅱ *
思路分析我说句题外话，就是何时使用【回溯】，何时使用【动态规划】，用大白话说，就是：
首先看取值范围，递归回溯一维数组，100就是深度的极限了（何况本题是100²）
如果是求走迷宫的【路径】，必然是回溯；如果是走迷宫的【路径的条数】，必然是dp--------(这个竟然屡试不爽！！！！)
与T62相比 只要遇到障碍就为0 具体体现在初始化和递推公式
代码实现
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){return 0;//特殊情况 起点和终点有障碍}//初始化 在没有遇到障碍前 左一列 上一行均为1for (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;}//递归公式for (int i = 1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==0){dp[i][j]= dp[i-1][j]+ dp[i][j-1];}else{dp[i][j] = 0;}}}return dp[m-1][n-1];}}
三、01背包
理论简介
问题描述有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。二维dp数组
数组含义： dp[ i ][ j ] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
递推公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
初始化 dp[0][j] 和 dp[i][0]
递推顺序 先物品或者背包都可以 建议采用先物品一维dp数组
数组含义：容量为j的背包，所背的物品价值可以最大为dp[j]
递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
初始化： dp[0]=0
遍历顺序必须先物品后背包，且背包要采用倒叙遍历
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]);}}
T416. 分割等和子集(背包能否装满) **
思路分析
就是数组和的一半, target=sum/2
每一个元素的数值既是重量，也是价值
dp[j]表示 背包总容量（所能装的总重量）是j，dp[j]表示 背包总容量（所能装的总重量）是j
代码实现
class Solution {public boolean canPartition(int[] nums) {int sum = 0;int target = 0;for (int i=0;i<nums.length;i++){sum = sum + nums[i];}if( sum%2!=0){return false;}//奇数else{target=sum/2;}int[] dp = new int[target+1];for(int i =0;i<nums.length;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;}}
T1049. 最后一块石头的重量Ⅱ(背包最多装多少) ***
思路分析难点在于分析转换为01问题
问题的本质在于尽量让石头分为两堆质量相同的
因此就是求dp[j]最多能装多少
与上一题区别在于上题相当于是求背包是否正好装满，而本题是求背包最多能装多少。代码实现
class Solution {//尽量把石头分为两堆质量相同public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i=0;i<stones.length;i++){sum += stones[i];}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]);//得到一半石头的最大重量}}return sum - 2 * dp[target];}}
T494. 目标和(装满背包有多少种方法 有统一公式！) ***
思路分析(背包问题求组合问题)难点一:变成背包问题
设求的和为x，x-(sum-x) = target … x = （target+sum)/2
问题转换为装满背包为x的背包有多少种方法
dp[j] 装满质量为j的背包有多少种方法，递推公式:取nums[i]，dp[j-nums[i]] 不取nums[i]
dp[j] += dp[j - nums[i]]
难点二:关于求出x后的一些细节
target>sum(绝对值)
x不是整数，则无法实现
代码实现
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i=0;i<nums.length;i++){sum += nums[i];}//记加法为x，减法为y，有x+y=sum，x-y=target；//x= (sum+target)/2if ((sum+target)%2!=0){return 0;} //若无法平分 则不存在if ((target<0&&sum<-target) || (target>0&&sum<target)){return 0;}//target比sum大 不存在int size = (sum+target)/2; //背包容量if (size<0){size = -size;} //负数转正int[] dp = new int[size+1];dp[0] = 1;for(int i=0;i<nums.length;i++){for(int j = size;j>=nums[i];j--){dp[j] += dp[j-nums[i]];}}return dp[size];}}
T474. 一和零 (两个维度的01背包) **
思路分析典型的01背包，只不过是两个维度
最多能装多少个代码实现
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(String str:strs){//遍历物品int zeroNum = 0;int oneNum = 0;for (char c: str.toCharArray()){if(c=='1'){oneNum++;}else{zeroNum++;}}//计算物品重量即1和0的个数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];}}
四、完全背包
理论简介
问题描述
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
解决方案
对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
如果问装满背包有几种方式的话？遍历顺序
组合数，(1，1，2)和（2，1，1）算一种情况，那就必须是 先物品后背包 排列数，必须是 先背包后物品
代码实现
//先遍历物品，再遍历背包private static void testCompletePack(){int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWeight = 4;int[] dp = new int[bagWeight + 1];for (int i = 0; i < weight.length; i++){// 遍历物品for (int j = weight[i]; j <= bagWeight; j++){// 遍历背包容量dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}for (int maxValue : dp){System.out.println(maxValue + " ");}}//先遍历背包，再遍历物品private static void testCompletePackAnotherWay(){int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWeight = 4;int[] dp = new int[bagWeight + 1];for (int i = 1; i <= bagWeight; i++){// 遍历背包容量for (int j = 0; j < weight.length; j++){// 遍历物品if (i - weight[j] >= 0){dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);}}}for (int maxValue : dp){System.out.println(maxValue + " ");}}
T518. 零钱兑换Ⅱ（装满背包有多少种方式 有统一公式！组合数！遍历顺序）***
思路分析比如 2，2，1 与 2，1，2是没区别的
遍历顺序必须是先物品后背包
dp[j]：凑成总金额j的货币组合数为dp[j]，dp【0】=1代码实现
class Solution {public int change(int amount, int[] coins) {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++){//j从coins【i】开始dp[j] += dp[j-coins[i]];}}return dp[amount];}}
T377. 组合总和Ⅳ（装满背包有多少种方法 排列数！遍历顺序）***
思路分析完全背包求装满背包有多少种方法，公式都是一样的，难点在于是排列数和组合数的遍历顺序不同
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。代码实现
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target+1];dp[0] = 1;for(int i=0;i<=target;i++){for(int j=0;j<nums.length;j++){if(i>=nums[j]){dp[i] += dp[i-nums[j]];}}}return dp[target];}}
T70. 爬楼梯(装满背包多少种方法,排列数) **
思路分析相当于装满重量为n的背包有多少种方法，且是排列数代码实现
class Solution {public int climbStairs(int n) {int[] dp = new int[n+1];int[] weight = {1,2};dp[0] = 1;for(int i =1;i<=n;i++){//跟顺序无关,先包后物品for(int j=0;j<weight.length;j++){if(i>=weight[j]){dp[i] += dp[i-weight[j]];}}}return dp[n];}}
T322. 零钱兑换(装满背包最少多少件东西) **
思路分析本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！代码实现
class Solution {//1. dp[j] 凑到金额j所需的最少硬币个数//2. dp[0] = 0 其他为最大值//3. dp[j] = min (dp[j-coins[i]] + 1, dp[j])//4. 先硬币后总金额public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];dp[0] = 0;for (int i = 1;i<dp.length;i++){dp[i] = Integer.MAX_VALUE;}for (int i = 0;i<coins.length;i++){for (int j = coins[i];j <= amount;j++){if (dp[j-coins[i]]!= Integer.MAX_VALUE){dp[j] = Math.min( dp[j-coins[i]] + 1 , dp[j]);}}}if (dp[amount] == Integer.MAX_VALUE){return -1;}return dp[amount];}}
T279. 完全平方数(装满背包最少多少件东西) **
思路分析完全平方数—物品,无限使用
n----背包重量
初始化: 为了取最小值，初始化为最大值
递推公式：取和不取两种情况代码实现
class Solution {public int numSquares(int n) {int[] dp = new int[n+1];//和为j的完全平方数的最少数量dp[0] = 0;for (int i=1;i<dp.length;i++){dp[i] = Integer.MAX_VALUE;}//初始化for (int i = 1;i*i<=n;i++){//遍历物品for (int j = i*i;j<=n;j++){if (dp[j-i*i]!=Integer.MAX_VALUE){dp[j] = Math.min(dp[j-i*i]+1,dp[j]);}}}return dp[n];}}
T139. 单词拆分(能否把背包装满) ****
思路分析单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
难点本题求的是排列数，物品顺序影响结果，所以一定是先背包后物品代码实现
class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];dp[0] = true;for (int j = 1;j<=s.length();j++){for(String word:wordDict){int length = word.length();if (j>=length && dp[j-length]==true && word.equals(s.substring(j-length,j))){dp[j] = true;break;}}}return dp[s.length()];}}
五、打家劫舍
T198. 打家劫舍(相邻) *
思路分析偷与不偷代码实现
class Solution {public int rob(int[] nums) {if (nums.length==1){return nums[0];}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] = Math.max(dp[i-2]+nums[i],dp[i-1]);}return dp[nums.length-1];}}
T213. 打家劫舍Ⅱ(相邻、带环) **
思路分析与原来相比加了个环，就有三种情况:不考虑第一个元素，不考虑最后一个元素，不考虑第一和最后一个元素，且三种情况可以合并
分两种情况算，再取最大值就好，注意一下下标得对应上就可代码实现
class Solution {//打家劫舍变形public int rob(int[] nums) {int len = nums.length;if (len == 1){return nums[0];}if (len == 2){return Math.max(nums[0],nums[1]);}int left = robHelper(nums,0,len-1);//不考虑最后一个int right = robHelper(nums,1,len);//不考虑第一个return Math.max(left,right);}public int robHelper(int[] nums,int start,int end){int[] dp = new int[end-start];dp[0] = nums[start];dp[1] = Math.max(nums[start],nums[start+1]);for(int i=2;i<end-start;i++){if(start==0){dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);}if(start==1){dp[i] = Math.max(dp[i-2]+nums[i+1],dp[i-1]);}}return dp[end-start-1];}}
T337. 打家劫舍Ⅲ (树形dp,后序遍历) **
思路分析看似神秘，实则简单
先来考虑遍历顺序，显然要从上到下处理这颗树，那么该节点偷还是不偷，取决于左右节点，因此必须采用后序 左右中，这样在处理中的时候已经有了左右的信息代码实现
class Solution {public int rob(TreeNode root) {int[] result = robHelper(root);return Math.max(result[0],result[1]);}public int[] robHelper(TreeNode root){int[] dp = new int[2];if (root==null){return dp;}int[] left = robHelper(root.left); //左int[] right = robHelper(root.right); //右//处理中dp[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);//不偷该节点dp[1] = root.val + left[0] + right[0];return dp;}}
六、股票问题
T121. 买卖股票的最佳时机(买卖一次) *
买卖一次起点都是0，与买卖多次不同，递推公式注意区别
class Solution {public int maxProfit(int[] prices) {int len = prices.length;int[][] dp = new int[len][2];dp[0][0] = - prices[0];dp[0][1] = 0;int res = 0;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][0]+prices[i],0);//不持有股票res = Math.max(res,dp[i][1]);}return res;}}
T122. 买卖股票的最佳时机Ⅱ(买卖多次) *
dp分持有和不持有股票分析即可
class Solution {public int maxProfit(int[] prices) {int len = prices.length;int[][] dp = new int[len][2];dp[0][0] = -prices[0];//持有股票dp[0][1] = 0;//不持有股票for(int i=1;i<len;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1] = Math.max(dp[i-1][0] + prices[i], dp[i-1][1]);}return dp[len-1][1];}}
T123. 买卖股票的最佳时机Ⅲ（2次买入卖出） **
分四种情况讨论，第一次持有，不持有，第二次持有，不持有
初始化：第二次持有 初始化为 -prices[0]
class Solution {public int maxProfit(int[] prices) {int len = prices.length;int[][] dp = new int[len][4];dp[0][0] = - prices[0];//第一次持有dp[0][1] = 0; //第一次不持有dp[0][2] = - prices[0];dp[0][3] = 0;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]);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]);}return dp[len-1][3];}}
T188. 买卖股票的最佳时机Ⅳ(k次买入卖出) **** 前面的题套总结，可以只看此题
为了方便 此题引入状态0，表示不操作，前面的题目也可以引入，但是过于简单，笔者没有引入
class Solution {public int maxProfit(int k, int[] prices) {//为了不需要分类讨论，引入多一个状态量0//状态0表示不操作//奇数：持有//偶数：不持有int len = prices.length;if(len<2) return 0;int[][] dp = new int[len][2*k+1];//初始化for(int i=1;i<2*k+1;i+=2){dp[0][i] = -prices[0];}//递推for(int i=1;i<len;i++){for(int j=1;j<2*k+1;j+=2){dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i-1][j] + prices[i]);}}return dp[len-1][2*k];} }
T309. 最佳买卖股票时机含冷冻期
class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(len<2) return 0;int[][] dp = new int[len][4];//不操作/买入/卖出/冷冻期dp[0][1] = -prices[0];for(int i=1;i<len;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][3]);dp[i][1] = Math.max(dp[i-1][1],Math.max(dp[i-1][3],dp[i-1][0])-prices[i]);dp[i][2] = dp[i-1][1]+prices[i];dp[i][3] = dp[i-1][2];}return Math.max(dp[len-1][0],Math.max(dp[len-1][2],dp[len-1][3]));}}
T714. 买卖股票的最佳时机含手续费
七、子序列问题
0. 总结
操作两个序列时，往往dp[i][j] 表示的是i-1的序列和j-1的序列。且要注意序列连续和不连续带来的公式区别
1. 不连续子序列
T300. 最长上升子序列 **
思路分析
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。
初始化必须都是1，不要理所当然的认为0，还是要严谨点
代码实现
class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp,1);for(int i=0;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);}}}int res =0;for(int i = 0;i<nums.length;i++){res = Math.max(res,dp[i]);}return res;}}
T1143. 最长公共子序列 **
class Solution {//题718 找最长重复子数组，但是此题不需要连续，只要满足相对顺序就好，因此当元素不等时需要进一步判断//dp[i][j] 0到i-1 text1的字符串 和 0到j-1 text2的字符串 的最长公共子序列//为了方便初始化 本题统一初始化 为 len+1public int longestCommonSubsequence(String text1, String text2) {int lenA = text1.length();int lenB = text2.length();int res = 0;int[][] dp = new int[lenA+1][lenB+1];for(int i = 1;i<=lenA;i++){char charA = text1.charAt(i-1);//取字符 注意此处需要减去1for(int j = 1; j<=lenB;j++){char charB = text2.charAt(j-1);if(charA==charB){//若两个字符相等 则在减1的基础上加1dp[i][j] = dp[i-1][j-1] + 1;}else{//若字符不等 则取左上元素的最大值dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}if(res<dp[i][j]){res = dp[i][j];}}}return res;}}
T1035. 不相交的线 *** (难在转换题目意思)
本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
代码实现
class Solution {//本质是求最长公共子序列public int maxUncrossedLines(int[] nums1, int[] nums2) {int lenA = nums1.length;int lenB = nums2.length;int res = 0;int[][] dp = new int[lenA+1][lenB+1];for(int i = 1;i<=lenA;i++){for(int j = 1;j <= lenB; 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]);}if(res<dp[i][j]){res = dp[i][j];}}}return res;}}
2. 连续子序列
T674. 最长连续递增序列 *
class Solution {//参考题300:简单化//由于是连续的 只需要考虑前一个 而不需要遍历全部public int findLengthOfLCIS(int[] nums) {int n = nums.length;int result = 0;if (n == 1){return 1;}int[] dp = new int[n];//dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。for(int i = 0;i<n;i++){dp[i] = 1;}for(int i = 1;i<n;i++){if(nums[i]>nums[i-1]){dp[i] = dp[i-1] + 1;}if(result<dp[i]){result = dp[i];}}return result;}}
T53. 最大子序和 * (也可以贪心)
class Solution {public int maxSubArray(int[] nums) {if(nums.length == 0) return 0;int[] dp = new int[nums.length];dp[0] = nums[0];int res = nums[0];for(int i=1;i<nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);//取不取前面的if(res<dp[i]){res = dp[i];}}return res;}}```### T718. 最长重复子数组 (与编辑距离章节可以对比)**- **思路分析**==注意此时求得是连续的，所以当nums1[i]与nums2[j]不相同时，不能给其赋值，与后面的编辑距离有区别===- **代码实现**```javaclass Solution {public int findLength(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int[][] dp = new int[len1+1][len2+1];//i-1 的nums1 和 j-1的nums2的最长重复子数组//初始化for(int i=0;i<len1+1;i++){dp[i][0] = 0;}for(int j=1;j<len2+1;j++){dp[0][j] = 0;}int res = 0;for(int i=1;i<len1+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;}//不同时，由于是连续数组，所以必须不能取res = Math.max(dp[i][j],res);}}return res;}}
3. 编辑距离 (dp含义，递推公式都不好想) ****
T392. 判断子序列 **** (是否)
思路分析难点1：dp的含义不好想
dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
以i-1是为了计算方便难点2：递推公式
字符相同，那就是dp[i-1][j-1]+1
字符不同，就相当于 t要减去那个字符，dp[i][j-1\代码实现
class Solution {public boolean isSubsequence(String s, String t) {int lenA = s.length();int lenB = t.length();int[][] dp = new int[lenA+1][lenB+1];// i-1 结尾s和 j-1结尾t 相同子序列的长度for(int i = 1;i<=lenA;i++){char sChar = s.charAt(i-1);for(int j = 1;j<=lenB;j++){char tChar = t.charAt(j-1);if(sChar==tChar){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = dp[i][j-1];}}}if(dp[lenA][lenB] == lenA){return true;//当相同子序列长度等于s 则说明s是t的子序列}else{return false;}}}
T115. 不同的子序列 **** （个数）
思路分析dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
(人话，在s中找出匹配t的有多少种方法，也就是t是固定死的，s是灵活的，后边递推公式也变成s[i]可以取，也可以不取)
递推公式
当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
不等时，dp[i][j] = dp[i - 1][j];
初始化当j=0，dp[i][0] = 1 dp[0][j] = 0 注意dp[0][0] = 1代码实现
class Solution {//递推公式中相等的情况 与之前不同public int numDistinct(String s, String t) {//表示i-1结尾的字符串s中出现j-1结尾的字符串t的个数int[][] dp = new int[s.length()+1][t.length()+1];//初始化for(int i = 0;i<=s.length();i++){dp[i][0] = 1;//假设t为空字符串 出现个数为1}for(int j = 1;j<=t.length();j++){dp[0][j] = 0; //当s为空，t不为空，注意dp[0][0]=1}//递推公式for(int i =1;i<=s.length();i++){for(int j =1;j<=t.length();j++){if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + dp[i-1][j];//相等时 分为两部分//一部分是s取i元素(此时相当于原来s和t都少取一个元素的情况) 一部分是s不取i元素}else{dp[i][j] = dp[i-1][j];//此时相当于s不取i元素}}}return dp[s.length()][t.length()];}}
T583. 两个字符串的删除操作 **** （两个字符串都可操作）
思路分析(方法一)与上题相比 两个字符都可以操作
dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
递推公式难
相同，dp[i][j] = dp[i - 1][j - 1];
不同，
情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2思路分析(方法二)
转换为找最长公共子序列，递推公式比较好理解代码实现
class Solution {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=0;i<len1+1;i++){dp[i][0] = i;}for(int j=1;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] = Math.min(dp[i-1][j-1]+2,Math.min(dp[i-1][j],dp[i][j-1])+1);}}}return dp[len1][len2];}}
class Solution {//1143.最长公共子序列//dp[i][j] i-1字符串word1 和 j-1字符串word2 的最长公共子序列//步数 = 多余的字符public int minDistance(String word1, String word2) {int lenA = word1.length();int lenB = word2.length();int[][] dp = new int[lenA+1][lenB+1];int res = 0;for(int i = 1;i<=word1.length();i++){for(int j = 1;j<= word2.length();j++){if(word1.charAt(i-1) == 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]);}if (res<dp[i][j]){res = dp[i][j];}}}return lenA+lenB-2*res;}}
T72. 编辑距离 ****
思路分析dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
如果相同，不需要操作
如果不同，那就进行增删改三种操作(增删本质一样，比如ab，a -> a,b ->ab,ab)，取最小值
删word1 :dp[i-1][j]+1
删word2 dp[i][j-1]+1
改 dp[i-1][j-1]+1代码实现
class Solution {//dp[i][j] i-1 结尾的单词word1 变成 j-1结尾单词word2 的最少操作数//四种操作//当字符相等, 字符不等 增删换public int minDistance(String word1, String word2) {int lenA = word1.length();int lenB = word2.length();int[][] dp = new int[lenA+1][lenB+1];//初始化for(int i = 0;i<=lenA;i++){dp[i][0] = i;}for(int j = 1;j<=lenB;j++){dp[0][j] = j;}//递推公式for(int i = 1;i<=lenA;i++){for(int j = 1;j<=lenB;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],Math.min(dp[i-1][j],dp[i][j-1])) + 1;//换，删，增三种操作}}}return dp[lenA][lenB];}}
4. 回文
分清楚是否连续，能否删除某些元素
T647. 回文子串 ***
思路分析难点1：dp的含义 dp[i][j] i到j的字符串是否是回文串
难点2：递推公式的推导，分情况讨论s[i]与s[j] 以及i与j
s[i]与s[j]不等 直接false
相等,看i与j差多少 小于等于1，大于1
难点3：遍历顺序 从递推公式可以看出i是从后到前
代码实现
class Solution {public int countSubstrings(String s) {boolean[][] dp = new boolean[s.length()][s.length()];int res=0;for(int i = s.length()-1;i>=0;i--){//从后往前遍历for(int j = i;j<s.length();j++){//不相等为false 默认false不需要操作if(s.charAt(i)==s.charAt(j)){//相等时 进行判断if(j-i<=1){//二者小于1 aa，adp[i][j]=true;}else{//二者差大于1， abccba 判断 bccbdp[i][j]=dp[i+1][j-1];}}}}for(int i = 0;i<s.length();i++){for(int j=0;j<s.length();j++){if(dp[i][j]){res++;}}}return res;}}
T516. 最长回文子序列 ***
思路分析字符串s在[i, j] 范围内最长的回文子序列的长度为 dp[i][j]
难点:递推公式 (与前一题有所不同)
如果相同,dp[i+1][j-1] + 2
如果不相同，说明 i，j 找不到最长，只能在 i+1 或者 j-1代码实现
class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int res = 0;if (len == 1){return 1;}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(s.charAt(i)==s.charAt(j)){dp[i][j] = dp[i+1][j-1] + 2; // 字符相同}else{dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]); //字符不同}if(res<dp[i][j]){res = dp[i][j];}}}return res;}}
如果觉得《leetcode动态规划刷题总结》对你有帮助，请点赞、收藏，并留下你的观点哦！
