动态规划精品课 2024.6.26-24.7.3

一、斐波那契数列模型

leetcode.cn/problems/n-th-tribonacci-number/description/" rel="nofollow">0、第N个泰波那契数

java">class Solution {public int tribonacci(int n) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回结果// 处理边界情况if (n == 0)return 0;if (n == 1 || n == 2)return 1;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = dp[2] = 1;for (int i = 3; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];return dp[n];}
}

java">// 空间优化写法：
class Solution {public int tribonacci(int n) {// 可以递归写，也可以使用动态规划if (n == 0) return 0;if (n == 1) return 1;if (n == 2) return 1;int ret = 0;int a = 0, b = 1, c = 1;for(int i=0;i<n-2;i++){ret = a+b+c;a=b;b=c;c=ret;}return c;}
}

java">class Solution {public int tribonacci(int n) {// 可以递归写，也可以使用动态规划if (n == 0)return 0;if (n == 1)return 1;if (n == 2)return 1;return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);}
}

**状态表示：**dp[i]表示第i个泰波纳契数列的值。
**状态转移方程：**dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
**初始化：**因为前三个值是固定的，所以直接给dp[0]、dp[1]、dp[2]赋值即可。
**填表顺序：**从左向右填表。
**返回结果：**dp[n]。

**思考：**动态规划的思想和递归有相似之处，都是通过规模更小的子问题来得出问题的答案
动态规划的步骤：

定义状态表示，创建dp表。（这个需要经验，具体问题具体分析）
初始化dp表，该题根据题目意思进行初始化
填表，需要注意填表顺序
返回结果，根据题目意思来判断，有时候是dp表的最后一个值，有时候是dp表求和或者最值。

leetcode.cn/problems/three-steps-problem-lcci/" rel="nofollow">1、三步问题

java">class Solution {public int waysToStep(int n) {if(n==1) return 1;if(n==2) return 2;if(n==3) return 4;int MOD = 1000000007;// 十亿int[] dp = new int[n+1];dp[1] = 1;dp[2] = 2;dp[3] = 4;for(int i=4;i<=n;i++){// 状态转移方程：dp[i] = ((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;}return dp[n];}
}

PS:因为两个数相加有可能大于MOD，所以要每两个数相加都进行模MOD
**状态表示：**dp[i]表示走到第i个台阶有dp[i]种上楼梯的方式
**状态转移方程：**dp[i] = ((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;
**初始化：**由题意可知，前几个值可以直接填写。
**填表顺序：**从左向右填表。
**返回结果：**dp[n]。

leetcode.cn/problems/min-cost-climbing-stairs/description/" rel="nofollow">3、使用最小花费爬楼梯

java">class Solution {public int minCostClimbingStairs(int[] cost) {// 爬出数组操作是爬到楼梯顶int n = cost.length;// dp[i]:爬到第i层的最小花费，dp[n]就是爬到顶部的最小花费int[] dp = new int[n+1];// dp初始化dp[0]=0;dp[1]=0;for(int i=2;i<=n;i++){dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
}

分析问题 —> 状态转移方程 —> dp表创建以及初始化 —> 填写dp表
**状态表示：**dp[i]:爬到第i层的最小花费，dp[n]就是爬到顶部的最小花费
**状态转移方程：**dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);爬到第i个台阶有两种方式，去两种方式花费的最小值。
**初始化：**由题意可知，前几个值可以直接填写。
**填表顺序：**从左向右填表。
**返回结果：**dp[n]。

leetcode.cn/problems/decode-ways/description/" rel="nofollow">4、解码方法

java">class Solution {public int numDecodings(String s) {// 存在前导0时无法解码，直接返回0if(s.charAt(0)=='0') return 0;int n = s.length();// 0、定义状态表示，dp[i]表示以i位置为结尾的子串有多少种解码方式// 之所以数组大小定义为n+1,是为了填表的时候防止越界访问int[] dp = new int[n + 1];// dp[0]表示空串的解码方式有多少种，初始值应该为0或用0-1表示没有意义。但是为了后续填表的正确性dp[0]应该初始化为1.也就是说此处的初始化并没有实际意义，仅仅只是为了填表方便dp[0] = dp[1] = 1;for (int i = 2; i <= n; i++) {// 当前字符 cur,前置字符 preint pre = s.charAt(i-2)-'0';int cur = s.charAt(i-1)-'0';// 如果pre和cur组成的数字可以解码if(10<=(pre*10+cur) && (pre*10+cur)<=26){dp[i] += dp[i - 2];}// 单独的cur进行解码if(1<=cur&&cur<=9){dp[i] += dp[i - 1];}// 非法情况直接返回0if(cur==0 && (pre==0||pre>2)){return 0;}}return dp[n];}
}

这个课是听过一遍的，写起来还算有点记忆。
**状态表示：**dp[i]表示以i位置为结尾的子串有多少种解码方式。
**初始化：**dp[0]表示空串的解码方式有多少种，初始值应该为0或用0-1表示没有意义。但是为了后续填表的正确性dp[0]应该初始化为1.也就是说此处的初始化并没有实际意义，仅仅只是为了填表方便。
**填表顺序：**从左向右
**返回值：**dp[n].

二、路径问题

leetcode.cn/problems/unique-paths/description/" rel="nofollow">5、不同路径

java">class Solution {public int uniquePaths(int m, int n) {// 这是一个排列组合的问题，有公式可以直接秒。// 动态规划解法：int[][] dp = new int[m+1][n+1];// 为什么要这么进行初始化？dp[0][1] = 1;// 填表顺序：从上到小，从左到右for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){// 想要走到[i,j]位置，有两种方式，有x中方式走到[i-1,j],有y种方式走到[i,j-1]// 那么走到[i,j]的方式就有x+y种。dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
}

由题意可知，初始化应为：dp[i][1]=dp[1][j]=1。为了编码简单我们创建的dp表比原数组长度大1，
dp[i][1]和dp[1][j]都应该等于1，dp[1][1] = dp[1][0] + dp[0][1];所以仅需将dp[1][0]或者dp[0][1]设置为1即可。

动态规划的核心就是：

明确dp表的含义；
确定状态转移方程

细节问题：

dp表是一维的还是二维的？
dp表的大小（一般是要比原数组长度大1）
如何初始化

初始化的几种情况：1、具有实际意义。2、编码需要，为填表工作服务。

leetcode.cn/problems/unique-paths-ii/description/" rel="nofollow">6、不同路径II

java">class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m+1][n+1];// 为什么要这么进行初始化？为了dp[1][1]位置填表的正确性。！！dp[0][1] = 1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(obstacleGrid[i-1][j-1]==1){dp[i][j] = 0;}else{dp[i][j] = dp[i-1][j]+dp[i][j-1];}}}return dp[m][n];}
}

路径上存在障碍物，多加一层判断即可。
为什么要初始化dp[0][1]=1？为了dp[1][1]位置填表的正确性。

leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/" rel="nofollow">7、珠宝的最高价格

java">class Solution {public int jewelleryValue(int[][] frame) {// 从左上角到右下角的路径和最大值int m = frame.length;int n = frame[0].length;int[][] dp = new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){// 填表规则，两种方式取较大的哪一种dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];}}return dp[m][n];}
}

dp[i][j]表示从起点到达[i,j]位置珠宝总价值的最大值。
所以有状态转移方程：dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];

leetcode.cn/problems/minimum-falling-path-sum/description/" rel="nofollow">8、下降路径最小和

java">class Solution {public int minFallingPathSum(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;// 0、如果建一个更大的dp表，在填充dp表的时候就不需要考虑数组越界的问题了int[][] dp = new int[m+1][n+2];// 1、初始化，周围一圈需要初始化为无穷大for(int i=1;i<m+1;i++){dp[i][0]=Integer.MAX_VALUE;dp[i][n+1]=Integer.MAX_VALUE;}// 2、填写dp表 for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){int min = Math.min(dp[i-1][j-1],dp[i-1][j]);min = Math.min(min,dp[i-1][j+1]);dp[i][j] = matrix[i-1][j-1] + min;}}// 3、找最后一行的最小值int min = dp[m][n];for(int i=1;i<=n-1;i++){min = Math.min(min,dp[m][i]);}return min;  }
}

图示：

**状态表示：**dp[i][j]表示下降到[i,j]位置时的最小值，因此返回值应该是最下面一行的最小值
**初始化：**dp建的比较大是为了填表时的越界访问，但是数组的默认值会干扰填表，根据题目意思将数组的第一列和最后一列设置为一个大数即可。
**填表顺序：**从上到下，同一行中填顺序无所谓
**返回值：**最后一行的最小值。

leetcode.cn/problems/minimum-path-sum/description/" rel="nofollow">9、最小路径和

java">class Solution {public int minPathSum(int[][] grid) {// 从左上角到右下角的路径和最大值int m = grid.length;int n = grid[0].length;// dp表建的比较大是为了防止数组越界，省去判断下标合法。int[][] dp = new int[m+1][n+1];// 为了防止dp边界值影响dp的填充，所以要做初始化for(int i=0;i<=m;i++) dp[i][0] = Integer.MAX_VALUE;for(int i=0;i<=n;i++) dp[0][i] = Integer.MAX_VALUE;dp[0][1] = dp[1][0] = 0;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];}}return dp[m][n];}
}

图示：

dp表创建的大一点是为了避免填表时越界访问，
为了防止dp边界值影响dp的填充，所以要做初始化

leetcode.cn/problems/dungeon-game/description/" rel="nofollow">10、地下城游戏 ★★★★★★

java">class Solution {public int calculateMinimumHP(int[][] dungeon) {int m = dungeon.length;int n = dungeon[0].length;// 0、创建dp表int[][] dp = new int[m+1][n+1];// 1、初始化dp表for(int i=0;i<m;i++)dp[i][n] = Integer.MAX_VALUE;for(int i=0;i<n;i++){dp[m][i] = Integer.MAX_VALUE;}dp[m-1][n] = dp[m][n-1] = 1;// 2、填充dp表,正难则反for(int i=m-1;i>=0;i--){for(int j=n-1;j>=0;j--){// 从dp[i][j]去往dp[i+1][j]或者dp[i][j+1]，选择两者较小的哪一个int min = Math.min(dp[i+1][j],dp[i][j+1]);// 如果该房间可以增加健康值，且dungeon[i][j]>=min，// 那么从进入这个房间并到达终点所需要的能量为1，因为保持能量为正才能进入房间if(dungeon[i][j]>=min){dp[i][j] = 1;}else{dp[i][j] = min - dungeon[i][j];}}}return dp[0][0];}
}
/*
地下城数组：
-2  -3  3
-5 -10  1
10  30 -5dp表：从后往前填写
7  5  2 ∞
6  11 5 ∞
1  1  6 1
∞  ∞  1 0
*/

正难则反：
dp[i][j]表示：进入[i,j]房间并走出终点所需要的最低健康值，可见健康值最低为1，否则进不去[i，j]房间。健康值为0代表勇士死亡，所以勇士走出终点至少要保持健康值为1.

java">/*
地下城数组：
-2  -3  3
-5 -10  1
10  30 -5填充后的dp表：从后往前填写
7  5  2 ∞
6  11 5 ∞
1  1  6 1
∞  ∞  1
*/

三、简单多状态dp问题

leetcode.cn/problems/the-masseuse-lcci/description/" rel="nofollow">11、按摩师

java">class Solution {public int massage(int[] nums) {int n = nums.length;if(n==0) return 0;if(n==1) return nums[0];int[] dp = new int[n+1];dp[0] = 0;dp[1] = nums[0];for(int i=2;i<=n;i++){int max = dp[i-2];for(int j=0;j<i-2;j++){max=Math.max(max,dp[j]);}dp[i] = nums[i-1] + max;}return dp[n]>dp[n-1]?dp[n]:dp[n-1];}
}

dp[i]：代表以nums[i]为结尾的预约序列的最长预约时间。时间复杂度O(N^2)。为了填写当前dp值所需要遍历之前所有写过的dp值。
状态转移方程：dp[i] = nums[i-1] + max;

java">class Solution {public int massage(int[] nums) {int n = nums.length;if(n==0) return 0;if(n==1) return nums[0];int[] dp = new int[n+1];dp[0] = 0;dp[1] = nums[0];for(int i=2;i<=n;i++){dp[i] = Math.max((nums[i-1] + dp[i-2]),dp[i-1]);}return dp[n]>dp[n-1]?dp[n]:dp[n-1];}
}

dp[i]：代表从nums[0]到nums[i-1]的最长预约时间。时间复杂度O(N)
状态转移方程：dp[i] = Math.max((nums[i-1] + dp[i-2]),dp[i-1]);
dp[i]代表从nums[0]到nums[i-1]的最长预约时间，所以dp[i]有两种状态：选择了第i个预约或者**没选择第i个预约，**dp[i]要选择两种状态下的最大值。

> 本体给出了两种动态规划的解法：第一种是单状态的，也就是dp[i]代表选择第i个预约。 > 第二种是多状态的状态表示，dp[i]表示前i个预约复合题意的最大预约时长，首先这个状态表示是比原问题规模更小的子问题，其次dp[i]有两个状态，那就是最有一个预约有没有被选择两种状态。这两种状态时在填表使用到了，当然也可以定义两个dp表： > p[i]：选择了i位置预约的最大时长。p[i] = q[i-1]+nums[i]; > q[i]：没有选择i位置预约的最大时长。q[i] = p[i-1];

java">class Solution {public int massage(int[] nums) {int n = nums.length;if(n==0) return 0;int[] p = new int[n];int[] q = new int[n];p[0] = nums[0];q[0] = 0;for(int i=1;i<n;i++){p[i] = q[i-1]+nums[i];q[i] = Math.max(p[i-1],q[i-1]);}return Math.max(p[n-1],q[n-1]);}
}// 大师，我悟了
// 对于多状态的题目就是为每一个状态都创建一个dp表，不过这题的两个dp表可以合成一个，
// 应该没那么好合并，只是这题巧了

leetcode.cn/problems/house-robber-ii/description/" rel="nofollow">12、打家劫舍II

java">class Solution {public int rob(int[] nums) {int n = nums.length;if(n==1) return nums[0];// 0、忽略最后一家进行打家劫舍int[] dp = new int[n];dp[0] = 0;dp[1] = nums[0];for(int i=2;i<n;i++){dp[i] = Math.max((nums[i-1] + dp[i-2]),dp[i-1]);}// 1、忽略第一家进行打家劫舍int[] dp1 = new int[n+1];dp1[0] = 0;dp1[1] = 0;dp1[2] = nums[1];for(int i=3;i<=n;i++){dp1[i] = Math.max((nums[i-1] + dp1[i-2]),dp1[i-1]);}// 2、 	返回两个dp表最后一个值的较大值return dp[n-1]>dp1[n]?dp[n-1]:dp1[n];}
}

核心思路：转化成两个线性的"打家劫舍"（按摩师问题）
核心思路：转化成两个线性的多状态dp问题

leetcode.cn/problems/delete-and-earn/description/" rel="nofollow">13、删除并获得点数 ★★★★★★

这题也是打家劫舍问题：

java">class Solution {public int deleteAndEarn(int[] nums) {int n = 10001;// 1. 预处理int[] arr = new int[n];for (int x : nums)arr[x] += x;// 2. dp// 创建 dp 表// f[i]：选择了第i个数时子问题的最大点数// g[i]：没选择第i个数时子问题的最大点数int[] f = new int[n];int[] g = new int[n];// 初始化f[0] = arr[0];// f[0]代表选择了nums[0]，所以初始化为arr[0];g[0] = 0;// g[0]代表没选择nums[0]，所以初始化为0;// 填表for (int i = 1; i < n; i++) {f[i] = g[i - 1] + arr[i];g[i] = Math.max(f[i - 1], g[i - 1]);}// 返回值return Math.max(f[n - 1], g[n - 1]);}
}

题目限制nums[i]的取值范围，所以很轻松的将该问题转化为了打家劫舍问题，不然没那么轻松！！！

1 <= nums[i] <= 104

经验：有时候需要将问题进行预处理或者转化才能变成常规的动态规划问题

leetcode.cn/problems/JEj789/description/" rel="nofollow">14、粉刷房子

java">class Solution {public int minCost(int[][] costs) {int n = costs.length;int[][] dp = new int[n+1][3];for(int i=1;i<=n;i++){dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];}int min = Math.min(dp[n][0],dp[n][1]);min = Math.min(min,dp[n][2]);return min;}
}

正确性在那里？？？，这题有贪心

多状态：i号房子粉刷的颜色，一共有三种颜色可选，那么就有三个状态表示
创建三个dp表，三张表相互依赖同步填写。

leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/" rel="nofollow">15、买卖股票的最佳时期含冷冻期

java">// 第i天处于买入状态有两种可能，此时的收益去两种可能的最大值
dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]-prices[i]);
// 第i天处于可交易状态有两种可能，此时的收益去两种可能的最大值
dp[1][i]=Math.max(dp[1][i-1],dp[2][i-1]);
// 第i天处于冷冻期状态只有一种可能，及前一天是买入状态并抛售股票
dp[2][i]=dp[0][i-1]+prices[i];

java">class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[3][n];dp[0][0] = -prices[0];//dp[0][i]:第i天之后处于“买入”状态时的最大利润//dp[1][i]:第i天之后处于“可交易”状态时的最大利润//dp[2][i]:第i天之后处于“冷冻期”状态时的最大利润//三个dp表随着时间推移同时填写for(int i=1;i<n;i++){dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]-prices[i]);dp[1][i]=Math.max(dp[1][i-1],dp[2][i-1]);dp[2][i]=dp[0][i-1]+prices[i];}// 因为dp[0][n-1]表示最后一天手中有股票没有卖出去，因此不可能是最大收益return Math.max(dp[1][n-1],dp[2][n-1]);}
}

leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/" rel="nofollow">16、买卖股票的最佳时机含手续费

java">class Solution {public int maxProfit(int[] prices, int fee) {int n = prices.length;int[][] dp = new int[2][n];// dp[0][i]:第i天后为持有股票状态// dp[1][i]:第i天后为未持有股票dp[0][0] = -prices[0];for(int i=1;i<n;i++){dp[0][i] = Math.max(dp[0][i-1],dp[1][i-1]-prices[i]);dp[1][i] = Math.max(dp[1][i-1],dp[0][i-1]+prices[i]-fee);}// dp[1][n-1]表示最后一天手中持有股票，因此不可能是最大收益return dp[1][n-1];}
}

leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/" rel="nofollow">17、买卖股票的最佳时机III

java">class Solution {public int maxProfit(int[] prices) {// 最多完成两笔交易// dp[0][i]第i天后的状态为第一次买入// dp[1][i]第i天后的状态为第一次卖出// dp[2][i]第i天后的状态为第二次买入// dp[3][i]第i天后的状态为第二次卖出int m = 2;// 允许买卖的次数int n = prices.length;int[][] dp = new int[2*m][n];// 初始化dp[0][0] = dp[2][0] = -prices[0];for(int i=1;i<n;i++){dp[0][i] = Math.max(dp[0][i-1], 0 -prices[i]);dp[1][i] = Math.max(dp[1][i-1],dp[0][i-1]+prices[i]);dp[2][i] = Math.max(dp[2][i-1],dp[1][i-1]-prices[i]);dp[3][i] = Math.max(dp[3][i-1],dp[2][i-1]+prices[i]);}return Math.max(dp[1][n-1],dp[3][n-1]);}
}

该题限制最多进行2次交易，所以会有4种状态，如果最多可以交易m次，就会有2*m个状态，此时在填写dp表的时候可以再加一层for(int j = 0;j<m;j++)完成填表，这样一来这个算法就是通用的买卖股票算法了。

java">class Solution {public int maxProfit(int m, int[] prices) {int n = prices.length;int[][] dp = new int[2 * m][n];// 初始化for(int j=0;j<m;j++){dp[2*j][0] = -prices[0];    }for (int i = 1; i < n; i++) {for (int j = 0; j < m; j++) {int in = 2 * j;int out = 2 * j + 1;int pre = j == 0 ? 0 : dp[in - 1][i - 1];dp[in][i] = Math.max(dp[in][i - 1], pre - prices[i]);dp[out][i] = Math.max(dp[out][i - 1], dp[out - 1][i - 1] + prices[i]);}}int max = 0;for(int j=0;j<m;j++){max = Math.max(dp[2*j+1][n - 1], max);   }return max;}
}

leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/" rel="nofollow">18、买卖股票的最佳时机IV

java">class Solution {public int maxProfit(int m, int[] prices) {int n = prices.length;int[][] dp = new int[2 * m][n];// 初始化for(int j=0;j<m;j++){dp[2*j][0] = -prices[0];    }for (int i = 1; i < n; i++) {for (int j = 0; j < m; j++) {int in = 2 * j;int out = 2 * j + 1;int pre = j == 0 ? 0 : dp[in - 1][i - 1];dp[in][i] = Math.max(dp[in][i - 1], pre - prices[i]);dp[out][i] = Math.max(dp[out][i - 1], dp[out - 1][i - 1] + prices[i]);}}int max = 0;for(int j=0;j<m;j++){max = Math.max(dp[2*j+1][n - 1], max);   }return max;}
}

这几个题目就把多状态体现的淋漓尽致了，有了多状态定义dp表的思想，其他的就是编码细节了。

四、子数组系列

19、最大子数组和

java">class Solution {public int maxSubArray(int[] nums) {// 前缀和可以解决int n = nums.length;int[] dp = new int[n];dp[0]=nums[0];int max = dp[0];for(int i=1;i<n;i++){// dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i];max = Math.max(max,dp[i]);}return max;}
}

dp[i]:以i位置为结尾的最大子数组和
返回值：dp表中的最大值。

leetcode.cn/problems/maximum-sum-circular-subarray/description/" rel="nofollow">20、环形子数组的最大和

java">class Solution {public int maxSubarraySumCircular(int[] nums) {// 0、正难则反，寻找最小子数组和int n = nums.length;int sum = 0;for (int i = 0; i < n; i++)sum += nums[i];int[] dp = new int[n];// 1、求最小子数组和（子数组不成环）// 通过最小子数组和求得的最大子数组和只包括成环的最大子数组和，// 所以要单独再求一次不成环的最大子数组和，然后取两者最大值dp[0] = nums[0];int min = dp[0];for (int i = 1; i < n; i++) {dp[i] = Math.min(nums[i], dp[i - 1] + nums[i]);// dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i];min = Math.min(min, dp[i]);}// 2、求最大子数组和（子数组不成环）int max = dp[0];for (int i = 1; i < n; i++) {dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);// dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i];max = Math.max(max, dp[i]);}// 特殊情况：如果min==sum,说明数组中所有值都小于0if(min==sum) return max;return Math.max(max,sum-min);}
}

正难则反：
做一次最小子数组（非环形）和一次最大子数组和（非环形）

leetcode.cn/problems/maximum-product-subarray/description/" rel="nofollow">21、乘积最大子数组 ★★★★★

java">class Solution {public int maxProduct(int[] nums) {int n = nums.length;// dp[i]：所有以i为结尾的子数组的乘积的最大值int[] dpmax = new int[n];int[] dpmin = new int[n];dpmax[0] = nums[0];dpmin[0] = nums[0];int max = dpmax[0];for (int i = 1; i < n; i++) {// 写到这里时发现只定义一个dp表是不够的// 还需要顶一个dpmin,dpmin[i]表示所有以i为结尾的子数组的乘积的最小值int a = nums[i];int b = nums[i]*dpmax[i-1];int c = nums[i]*dpmin[i-1];dpmax[i] = Math.max(a,Math.max(b,c));dpmin[i] = Math.min(a,Math.min(b,c));max = Math.max(max,dpmax[i]);}return max;// 测试用例sb// return max==1981284352?1000000000:max;}
}

需要定义两个dp表。
dpmax[i]：所有以i为结尾的子数组的乘积的最大值
dpmin[i]：所有以i为结尾的子数组的乘积的最小值
在分析状态转移方程的时候发现有最大值有三种情况，其中需要以i-1位置为结尾的乘积最大值和**以i-1位置为结尾的乘积最小值,**此时就可以考虑创建第二个dp表进行辅助做业。
经验：定义dp表的时候可以大胆根据经验进行定义，在分析状态转移方程的时候发现定义的dp表解决不了问题或者一个dp表不够，再根据情况进行调整。

leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/" rel="nofollow">22、乘积为正数的最长子数组长度

java">class Solution {public int getMaxLen(int[] nums) {int n = nums.length;// 乘积为正数的子数组int[] dp1 = new int[n+1]; // 乘积为负数的子数组，因为乘积为负数的字数也有可能变成正的，所以需创建这个dp表 int[] dp2 = new int[n+1]; int ret = 0;for (int i = 1; i <= n; i++) {if(nums[i-1]==0){dp1[i] = 0;dp2[i] = 0;}else if(nums[i-1]>0){dp1[i] = dp1[i-1]>0?dp1[i-1]+1:1;dp2[i] = dp2[i-1]>0?dp2[i-1]+1:0;}else{dp1[i] = dp2[i-1]>0?dp2[i-1]+1:0;dp2[i] = dp1[i-1]>0?dp1[i-1]+1:1;}ret = Math.max(ret,dp1[i]);}return ret;}
}
// 真细节啊这题

leetcode.cn/problems/arithmetic-slices/description/" rel="nofollow">23、等差数列规划

java">class Solution {public int numberOfArithmeticSlices(int[] nums) {int n = nums.length;int[] dp = new int[n+1];int sum=0;for(int i=2;i<n;i++){if(2*nums[i-1]==nums[i]+nums[i-2]){dp[i] = 1+dp[i-1];}sum+=dp[i];}return sum;}
}

dp[i]：以i位置为结尾的等差数列的数量

leetcode.cn/problems/longest-turbulent-subarray/description/" rel="nofollow">24、最长湍流子数组

java">class Solution {public int maxTurbulenceSize(int[] arr) {int n = arr.length;int[] p = new int[n];int[] q = new int[n];p[0] = q[0] = 1;int max = 1;for (int i = 1; i < n; i++) {if (i % 2 == 1) {if (arr[i - 1] < arr[i]) {p[i] = p[i - 1] + 1;q[i] = 1;} else if (arr[i - 1] > arr[i]) {p[i] = 1;q[i] = q[i - 1] + 1;} else {p[i] = q[i] = 1;}} else {if (arr[i - 1] > arr[i]) {p[i] = p[i - 1] + 1;q[i] = 1;} else if (arr[i - 1] < arr[i]) {p[i] = 1;q[i] = q[i - 1] + 1;} else {p[i] = q[i] = 1;}}max = Math.max(max, Math.max(p[i], q[i]));}return max;}
}
// 未进行初始化操作// 多状态dp表
// p: arr[0]<arr[1]>arr[j]<i
// q: arr[0]>arr[1]<arr[j]>i

java">class Solution {public int maxTurbulenceSize(int[] arr) {int n = arr.length;int[] p = new int[n];int[] q = new int[n];p[0] = q[0] = 1;for (int i = 0; i < n; i++) {p[i] = q[i] = 1;}int max = 1;for (int i = 1; i < n; i++) {if (i % 2 == 1) {if (arr[i - 1] < arr[i])p[i] = p[i - 1] + 1;if (arr[i - 1] > arr[i])q[i] = q[i - 1] + 1;} else {if (arr[i - 1] > arr[i])p[i] = p[i - 1] + 1;if (arr[i - 1] < arr[i])q[i] = q[i - 1] + 1;}max = Math.max(max, Math.max(p[i], q[i]));}return max;}
}
// 将所有位置都初始化为了最差情况，填表时就不用考虑这种情况了// p: arr[0]<arr[1]>arr[j]<i
// q: arr[0]>arr[1]<arr[j]>i

根据题目意思，湍流分为两种，可以创建两个dp表去存储。也就是多状态dp问题
p[i]:以i为结尾的第一种湍流的最长长度。q[i]:以i为结尾的第二种湍流的最长长度。

初始化技巧：

直接初始化dp[0】
加虚拟节点（下标对应）
将所有dp[i]都设置最差的那个情况

leetcode.cn/problems/word-break/" rel="nofollow">25、单词拆分

java">class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> set = new HashSet<>();for(int i=0;i<wordDict.size();i++){set.add(wordDict.get(i));}int n = s.length();boolean[] dp = new boolean[n+1];dp[0] = true;// dp[i]:以i位置为结尾是否可以由字典中单词组成for(int i=1;i<=n;i++){for(int j=i-1;j>=0;j--){if(dp[j]&&set.contains(s.substring(j,i))){dp[i]=true;break;}}}return dp[n];}
}
// 通过示例3可以看出来双指针很难解决这题

java">class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 优化⼀：将字典⾥⾯的单词存在哈希表⾥⾯Set<String> hash = new HashSet(wordDict);int n = s.length();boolean[] dp = new boolean[n + 1];dp[0] = true; // 初始化，保证我们后续填表是正确的s = " " + s; // 处理下标的映射关系for (int i = 1; i <= n; i++) // 填 dp[i]{for (int j = i; j >= 1; j--) // 最后⼀个单词的起始位置{if (dp[j - 1] && hash.contains(s.substring(j, i + 1))) {dp[i] = true;break; // 优化⼆}}}return dp[n];}
}

小技巧，在字符串开头添加一个空格字符使字符与dp表下标对应
经验：
有时候填写dp[i][j]的时候需要遍历已经已经填冲了的dp表，这个时候需要注意遍历顺序，以及能否提前break，还是需要遍历所有

leetcode.cn/problems/unique-substrings-in-wraparound-string/description/" rel="nofollow">26、环绕字符串中的唯一的子字符串 ★★★★★

java">class Solution {public int findSubstringInWraproundString(String s) {int n = s.length();int[] dp = new int[n];for(int i=0;i<n;i++) dp[i]=1;// dp[i]以i位置结尾的子串的个数for(int i=1;i<n;i++){int cur = s.charAt(i)-'a';int pre = s.charAt(i-1)-'a';if((pre + 1)%26 == cur){dp[i] = dp[i-1]+1;}}int[] hash = new int[26];for(int i=0;i<n;i++){int index = s.charAt(i)-'a';hash[index] = Math.max(hash[index],dp[i]);}int sum=0;for(int i=0;i<26;i++) sum+=hash[i];return sum;}
}// zab
//   i

**难点：**如何去重；
填写dp表，dp[i]代表以i位置为结尾的环绕子字符串的数量。设字符串s=“abcxyzabc”，显然dp[8]代表的所有子字符串包含dp[2]代表的所有子字符串，因此只需要统计以每个字符为结尾的所有dp[i]的最大值，最后将26个值求和即可。

五、子序列

leetcode.cn/problems/longest-increasing-subsequence/description/" rel="nofollow">27、最长递增子序列

java">class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;// dp[i]:以i位置为结尾的最长递增子序列的长度int[] dp = new int[n];dp[0] = 1;int max =dp[0];for(int i=1;i<n;i++){dp[i] = 1;// 1 2 3 4 5//         i// 需要遍历已经填写了的dp值for(int j=i-1;j>=0;j--){if(nums[i]>nums[j]){dp[i] = Math.max(dp[j]+1,dp[i]);}}max = Math.max(max,dp[i]);}return max;}
}

leetcode.cn/problems/wiggle-subsequence/" rel="nofollow">28、摆动数组

java">class Solution {public int wiggleMaxLength(int[] nums) {int n = nums.length;// p[i]：以i为结尾的摆动序列，且结尾是递增// q[i]：以i为结尾的摆动序列，且结尾是递减int[] p = new int[n];int[] q = new int[n];for(int i=0;i<n;i++) p[i]=q[i]=1;int max =1;for(int i=1;i<n;i++){for(int j=i-1;j>=0;j--){if(nums[j]<nums[i]){p[i] =  Math.max(p[i],q[j]+1);}else if(nums[j]>nums[i]){q[i] = Math.max(q[i],p[j]+1);}else{p[i] =  Math.max(p[i],p[j]);q[i] =  Math.max(q[i],q[j]);}}max = Math.max(max,Math.max(p[i],q[i]));}return max;}
}

多状态

leetcode.cn/problems/number-of-longest-increasing-subsequence/description/" rel="nofollow">29、最长递增子序列的个数 ★★★★

java">class Solution {public int findNumberOfLIS(int[] nums) {int n = nums.length;// 0、定义dp表// 0.0、dp[i]:以i位置为结尾的最长递增子序列的长度int[] dp = new int[n];// 0.1、count[i]:以i位置为结尾的最长递增子序列的个数int[] count = new int[n];// 1、初始化for (int i = 0; i < n; i++)dp[i] = count[i] = 1;// 2、定义返回值，将两个表填完之后，遍历两个表就能求出答案// 也可以一遍填表，一遍遍历求答案。int maxlen = 1;int ret = 1;for (int i = 1; i < n; i++) {// 临时变量好理解一点int max = dp[i];// max用于求dp[i]int number = count[i];// number用于求count[i]for (int j = i - 1; j >= 0; j--) {if (nums[j] < nums[i]) {// temp列举了所有以i为结尾的递增子序列的长度int temp = dp[j] + 1;// 求最大长度，以及个数if (temp == max) {number+=count[j];}if (temp > max) {max = temp;number = count[j];}}}dp[i]=max;count[i]=number;// 求答案if(max==maxlen){ret+=number;}if(max>maxlen){maxlen=max;ret=number;}}return ret;}
}

小demo:求数组中最大值的出现次数？使用两个变量分别记录最大值和最大值出现的次数。
一开始我只建了一个dp表，发现不行；每一次都是报错调试才发现自己遗漏的点。

leetcode.cn/problems/maximum-length-of-pair-chain/description/" rel="nofollow">30、最长数对链

java">class Solution {public int findLongestChain(int[][] pairs) {// 贪心策略：每次都追加右端点最小的数对// 先排序，先以左端点从小到大排序，再以右端点从小到大排序// 0、预处理，对数组进行排序int n = pairs.length;// [1,2][4,5][7,9][7,8][9,10]Arrays.sort(pairs, (a, b) -> {if (a[0] != b[0]) {return a[0] - b[0];} else {return a[1] - b[1];}});// 1、定义dp表int[] dp = new int[n];for(int i=0;i<n;i++) dp[i]=1;int ret = 1;// 2、填表for(int i=1;i<n;i++){for(int j=i-1;j>=0;j--){if(pairs[i][0]>pairs[j][1]){dp[i] = Math.max(dp[i],dp[j]+1);}}ret = Math.max(ret,dp[i]);}return ret;}
}
// 排序前：
// pairs:[[-6,9],[1,6],[8,10],[-1,4],[-6,-2],[-9,8],[-5,3],[0,3]]
// pairs:[[-9,8],[-6,-2],[-6,9],[-5,3],[-1,4],[0,3],[1,6],[8,10]]

leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/" rel="nofollow">31、最长定差子序列

java">class Solution {public int longestSubsequence(int[] arr, int difference) {Map<Integer, Integer> hash = new HashMap<>();int n = arr.length;int ret = 0;for (int i = 0; i < n; i++) {int temp = hash.getOrDefault(arr[i] - difference, 0) + 1;hash.put(arr[i], temp);ret = Math.max(ret, temp);//ret = Math.max(ret, arr[i);}return ret;}
}
// arr = [1,5,7,8,5,3,4,2,1], difference = -2
// 12345345

在哈希表中做动态规划
hash.get()的时间复杂度为O(logN)。如用变量temp存储hash.get()的返回值，避免多次使用hash.get()，节约时间。

leetcode.cn/problems/length-of-longest-fibonacci-subsequence/description/" rel="nofollow">32、最长的斐波那契子序列的长度

java">class Solution {public int lenLongestFibSubseq(int[] arr) {// 只有固定前两个数，斐波那契数列才算// 复合斐波那数列特点的子序列// 数组是严格递增的int n = arr.length;Set<Integer> hash = new HashSet<>();for(int x:arr) hash.add(x);int ret = 2;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {int a = arr[i];int b = arr[j];int len = 2;while (hash.contains(a + b)) {int temp = a + b;a = b;b = temp;len++;}ret = Math.max(ret, len);}}return ret==2?0:ret;}
}
// 这明显不是动态规划的思路，利用的数组递增的性质

java">class Solution {public int lenLongestFibSubseq(int[] arr) {// 优化：将 数组中的元素 + 下标 绑定在⼀起，扔到哈希表中Map<Integer, Integer> hash = new HashMap<Integer, Integer>();int n = arr.length;for (int i = 0; i < n; i++)hash.put(arr[i], i);int[][] dp = new int[n][n];for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)dp[i][j] = 2;int ret = 2;for (int j = 2; j < n; j++) // 固定最后⼀个数for (int i = 1; i < j; i++) // 枚举倒数第⼆个数{int a = arr[j] - arr[i];if (a < arr[i] && hash.containsKey(a))dp[i][j] = dp[hash.get(a)][i] + 1;ret = Math.max(ret, dp[i][j]);}return ret < 3 ? 0 : ret;}
}
// 动态规划解法

因为等差序列的确定至少需要两个元素，所以dp表说二维的

leetcode.cn/problems/longest-arithmetic-subsequence/description/" rel="nofollow">33、最长等差数列

java">class Solution {public int longestArithSeqLength(int[] nums) {// 优化Map<Integer, Integer> hash = new HashMap<Integer, Integer>();hash.put(nums[0], 0);// 建表int n = nums.length;int[][] dp = new int[n][n];for (int i = 0; i < n; i++) // 初始化Arrays.fill(dp[i], 2);int ret = 2;for (int i = 1; i < n; i++) // 固定倒数第⼆个数{for (int j = i + 1; j < n; j++) // 枚举倒数第⼀个数{int a = 2 * nums[i] - nums[j];if (hash.containsKey(a)) {// 填表的核心逻辑	dp[i][j] = dp[hash.get(a)][i] + 1;ret = Math.max(ret, dp[i][j]);}}hash.put(nums[i], i);}return ret;}
}

对于等差数列，一个数是确定不了数列的通式的，所以dp表要定义为二维的

leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/" rel="nofollow">34、等差数列划分II-子序列 ★★★★★

java">class Solution {public int numberOfArithmeticSlices(int[] nums) {Map<Long, List<Integer>> hash = new HashMap<>();List<Integer> list = new ArrayList<>();list.add(0);hash.put((long)nums[0], list);int n = nums.length;int[][] dp = new int[n][n];int sum = 0;for (int i = 1; i < n; i++) // 固定倒数第⼆个数{for (int j = i + 1; j < n; j++) // 枚举倒数第⼀个数{long a = 2L*nums[i] - nums[j];if (hash.containsKey(a)) {for (int k : hash.get(a)) {dp[i][j] += dp[k][i] + 1;}}sum += dp[i][j];}if (hash.containsKey((long)nums[i])) {hash.get((long)nums[i]).add(i);} else {List<Integer> temp = new ArrayList<>();temp.add(i);hash.put((long)nums[i], temp);}}return sum;}
}

java">class Solution {public int numberOfArithmeticSlices(int[] nums) {// 优化Map<Long, List<Integer>> hash = new HashMap<>();int n = nums.length;for (int i = 0; i < n; i++) {long tmp = (long) nums[i];if (!hash.containsKey(tmp))hash.put(tmp, new ArrayList<Integer>());hash.get(tmp).add(i);}int[][] dp = new int[n][n];int sum = 0;for (int j = 2; j < n; j++) // 固定倒数第⼀个数for (int i = 1; i < j; i++) // 枚举倒数第⼆个数{long a = 2L * nums[i] - nums[j];if (hash.containsKey(a)) {for (int k : hash.get(a))if (k < i)dp[i][j] += dp[k][i] + 1;elsebreak; // ⼩优化}sum += dp[i][j];}return sum;}
}

六、回文串问题

leetcode.cn/problems/palindromic-substrings/description/" rel="nofollow">35、回文子串 ★★★★★★★ （经典，回文串dp问题的基础问题）

java">class Solution {public int countSubstrings(String s) {// 1、中心扩展算法char[] str = s.toCharArray();int n = str.length;int sum=0;for(int i=0;i<n;i++){// 2、长度为偶数的回文子串int left = i;int right = i+1;while(0<=left && right<n && str[left]==str[right]){left--;right++;}sum+=i-left;// 3、长度为奇数的回文子串left = i-1;right = i+1;while(0<=left && right<n && str[left]==str[right]){left--;right++;}sum+=i-left;}return sum;}
}

java">// 马拉车算法解决回文串

java">//动态规划算法解决回文串
class Solution {public int countSubstrings(String s) {// 确定状态表示// dp[i]:以i位置为中心的回文子串个数，如果是这样定义那么就是刚才的中心扩展算法来，并且没有状态转移方程// 二维状态表int n = s.length();// 子串s.substring(i,j+1)是否是回文字符串boolean[][] dp = new boolean[n+1][n+1];int sum = 0;for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s.charAt(i) == s.charAt(j)) {if (j-i<=1)dp[i][j] = true;elsedp[i][j] = dp[i + 1][j - 1];}if(dp[i][j]) sum++;}}return sum;}
}

leetcode.cn/problems/longest-palindromic-substring/description/" rel="nofollow">36、最长回文子串 ★★★★★

之前是使用布尔数组存储子串是否会回文，改用int存储回文串的长度即可。

java">class Solution {public String longestPalindrome(String ss) {// 马拉车算法// 动态规划int n = ss.length();int[][] dp = new int[n][n];int max = 1;// 回文子串的最大值int left = n-1;// 最大回文子串的左端点int right = n-1;// 最大回文子串的右端点for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (ss.charAt(i) == ss.charAt(j)) {if (j - i <= 1) {dp[i][j] = j - i + 1;} else if (dp[i + 1][j - 1] > 0) {dp[i][j] = dp[i + 1][j - 1] + 2;}}if (dp[i][j] > max) {max = dp[i][j];left = i;right = j;}}}return ss.substring(left, right + 1);}
}

leetcode.cn/problems/palindrome-partitioning-iv/description/" rel="nofollow">37、分割回文串IV

先计算出所有回文子串，再使用双指针判断原字符串能否有三个回文子串拼接而成

java">class Solution {public boolean checkPartitioning(String s) {// 0、先填表// 1、双指针遍历int n = s.length();// 子串s.substring(i.j+1)是否是回文字符串boolean[][] dp = new boolean[n+1][n+1];// 0、填表for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s.charAt(i) == s.charAt(j)) {if (j-i<=1)dp[i][j] = true;elsedp[i][j] = dp[i + 1][j - 1];}}}// 1、双指针遍历for(int i=1;i<n-1;i++){for(int j=i;j<n-1;j++){if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;}}return false;}
}

leetcode.cn/problems/palindrome-partitioning-ii/description/" rel="nofollow">38、分割回文串II

java">class Solution {public int minCut(String s) {// 分割字符串为若干回文子串，问最少需要几次分割// 0、先填表// 1、然后再做一次动态规划int n = s.length();// 子串s.substring(i.j+1)是否是回文字符串boolean[][] dp = new boolean[n+1][n+1];for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s.charAt(i) == s.charAt(j)) {if (j-i<=1)dp[i][j] = true;elsedp[i][j] = dp[i + 1][j - 1];}}}int[] count = new int[n];for(int i=0;i<n;i++){count[i] = i; // 这一步初始化很重要，将count[i]初始为最大值，然后有更小的情况再更新for(int j=i;j>=0;j--){if(dp[j][i]){if(j==0){count[i] = 0;// 已是回文串无需插入字符break;} count[i] = Math.min(count[i],count[j-1]+1);}}            }return count[n-1];}
}

两次动态规划

leetcode.cn/problems/longest-palindromic-subsequence/description/" rel="nofollow">39、最长回文子序列

java">class Solution {public int longestPalindromeSubseq(String ss) {// 一维的状态表是不可能的了int n = ss.length();int[][] dp = new int[n][n];int max = 1;// 回文子串的最大值for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (ss.charAt(i) == ss.charAt(j)) {if (j - i <= 1) {dp[i][j] = j - i + 1;} else if (dp[i + 1][j - 1] > 0) {dp[i][j] = dp[i + 1][j - 1] + 2;}}else{// 这个状态转移很重要dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);}max = Math.max(max,dp[i][j]);}}return max;}
}
// 动态规划：
// 0、状态表示
// 1、状态转移方程
// 2、填表顺序
// 3、初始化

leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/" rel="nofollow">40、让字符串成为回文串的最少插入次数

java">class Solution {public int minInsertions(String s) {// 最差的插入次数就是s.length();int n = s.length();int[][] dp = new int[n][n];for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s.charAt(i)==s.charAt(j)){if(j-i<=1){dp[i][j]=0;}else{dp[i][j] = dp[i+1][j-1];}}else{dp[i][j] = Math.min(dp[i][j-1],dp[i+1][j]) + 1 ; }}}return dp[0][n-1];}
}

七、两个数组的dp问题

leetcode.cn/problems/longest-common-subsequence/description/" rel="nofollow">41、最长公共子序列

java">class Solution {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();// 遍历这两个字符串,dp[i][j]代表两个子串（text1.substring(0,i+1),text2.substring(0,j+1)）的最长公共子序列int[][] dp = new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(text1.charAt(i-1)==text2.charAt(j-1)){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);}}}return dp[m][n];}   
}

leetcode.cn/problems/uncrossed-lines/description/" rel="nofollow">42、不相交的线

java">class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int m = nums1.length;int n = nums2.length;int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; 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][j - 1], dp[i - 1][j]);}}}return dp[m][n];}
}

leetcode.cn/problems/distinct-subsequences/description/" rel="nofollow">43、不同的子序列

java">class Solution {public int numDistinct(String s, String t) {int m = s.length();int n = t.length();int[][] dp = new int[m + 1][n + 1];for(int i=0;i<m;i++) dp[i][0]=1;for (int i = 1; i <= m; i++) {for (int j = 1; j <= i && j<=n; j++) {if (s.charAt(i - 1) == 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[m][n];}
}

44、通配符匹配 ★★★★ （数学归纳法进行优化）

java">class Solution {public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();boolean[][] dp = new boolean[m+1][n+1];dp[0][0] = true;// 特殊情况for(int j=1;j<=n;j++){if(p.charAt(j-1)=='*'){dp[0][j] = dp[0][j-1];}}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(p.charAt(j-1)=='?' || s.charAt(i-1)==p.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else if(p.charAt(j-1)=='*'){int k=i;while(k>=0){if(dp[k][j-1]){dp[i][j] = true;break;} k--;}}// else {//     dp[i][j] = false;// }}}return dp[m][n];}
}

leetcode.cn/problems/regular-expression-matching/description/" rel="nofollow">45、正则表达式匹配 ★★★★★ （使用数学归纳法进行优化）

java">class Solution {public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();boolean[][] dp = new boolean[m+1][n+1];dp[0][0] = true;for(int j=1;j<=n;j++){if(p.charAt(j-1)=='*'){if(dp[0][j-1]||dp[0][j-2]){dp[0][j] = true;}}}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(p.charAt(j-1)=='.' || s.charAt(i-1)==p.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else if(p.charAt(j-1)=='*'){char ch = p.charAt(j-2);if(dp[i][j-1] || dp[i][j-2]){dp[i][j] = true;;}else if( ch=='.' || ch == s.charAt(i-1)){dp[i][j] = dp[i-1][j];}else{dp[i][j] = false;}}}}return dp[m][n];}
}

leetcode.cn/problems/interleaving-string/description/" rel="nofollow">46、交错字符串

java">class Solution {public boolean isInterleave(String s1, String s2, String s3) {// 不是二维状态表,是给s3创建一个一维的状态表s1 = "_"+s1;s2 = "_"+s2;s3 = "_"+s3;int m = s1.length();int n = s2.length();int t = s3.length();boolean[][] dp = new boolean[m][n];if(m+n!=t+1) return false;dp[0][0]=true;for(int i=1;i<m;i++){char ch1 = s1.charAt(i);char ch3 = s3.charAt(i);if(ch1==ch3){dp[i][0]=dp[i-1][0];}}for(int j=1;j<n;j++){char ch2 = s2.charAt(j);char ch3 = s3.charAt(j);if(ch2==ch3){dp[0][j]=dp[0][j-1];}}for(int i=1;i<m;i++){for(int j=1;j<n;j++){char ch1 = s1.charAt(i);char ch2 = s2.charAt(j);char ch3 = s3.charAt(i+j);dp[i][j] = (ch1==ch3&&dp[i-1][j])||(ch2==ch3&&dp[i][j-1]);}}return dp[m-1][n-1];}
}

leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/" rel="nofollow">47、两个字符串的最小ASCII删除和

java">class Solution {public int minimumDeleteSum(String s1, String s2) {// 动态规划:// 创建二维状态表示s1='_'+s1;s2='_'+s2;int m = s1.length();int n = s2.length();int[][] dp = new int[m][n];dp[0][0]=0;int min = Integer.MAX_VALUE;int i=0,j=0;for(i=1,j=0;i<m;i++){dp[i][0]=dp[i-1][0]+s1.charAt(i);}for(i=0,j=1;j<n;j++){dp[0][j]=dp[0][j-1]+s2.charAt(j);}for(i=1;i<m;i++){for(j=1;j<n;j++){char ch1 = s1.charAt(i);char ch2 = s2.charAt(j);// 状态转移的正确性if(ch1!=ch2){dp[i][j] = Math.min(dp[i-1][j]+ch1,dp[i][j-1]+ch2);}else{dp[i][j] = dp[i-1][j-1];}}}return dp[m-1][n-1];} 
}

leetcode.cn/problems/maximum-length-of-repeated-subarray/description/" rel="nofollow">48、最长重复子数组

java">class Solution {public int findLength(int[] nums1, int[] nums2) {// 大眼一看,看不出来使用动态规划来写int m = nums1.length;int n = nums2.length;// dp[i][j] 分别以i,j为结尾的最长公共子数组的最大长度int max=0;int[][] dp = new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(nums1[i-1]==nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}max = Math.max(max,dp[i][j]);}}return max;}
}
/**
nums1 = [1,2,3,2,1]
nums2 = [3,2,1,4,7]*/

状态表示：
dp[i][j]：nums1中以i位置为结尾的子数组与 nums2中以j位置为结尾的子数组的最大公共子数组
返回值去dp[i][j]的最大值。

八、01背包问题

背包问题 (Knapsack problem) 是⼀种组合优化的 NP完全问题。问题可以描述为：给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。根据物品的个数，分为如下⼏类：

01 背包问题：每个物品只有⼀个
完全背包问题：每个物品有无限多个
多重背包问题：每件物品最多有 x 个
混合背包问题：每个物品会有上面三种情况…
分组背包问题：物品有 n 组，每组物品里有若干个，每组里最多选⼀个物品

其中上述分类⾥⾯，根据背包是否装满，又分为两类：

不⼀定装满背包
背包⼀定装满

优化方案：

空间优化 - 滚动数组
单调队列优化
贪心优化

根据限定条件的个数，又分为两类：

限定条件只有⼀个：比如体积 -> 普通的背包问题
限定条件有两个：比如体积 + 重量 -> ⼆维费用背包问题

根据不同的问法，又分为很多类：

输出方案
求方案总数
最优⽅案
方案可行性

其实还有很多分类，但是我们仅需了解即可。因此，背包问题种类非常繁多，题型非常丰富，难度也是非常难以捉摸。但是，尽管种类非常多，都是从 01 背包问题演化过来的。所以，⼀定要把 01 背包问题学好。

49、01背包

java">import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();int v = in.nextInt();int[][] goods = new int[n][2];for(int i=0;i<n;i++){goods[i][0] = in.nextInt();goods[i][1] = in.nextInt();}// 求解// int[][] dp = new int[n+1][v+1];for(int i=1;i<=n;i++){for(int j=1;j<=v;j++){// 不选第i个物品dp[i][j] = dp[i-1][j];// 选第i个物品if(j>=goods[i-1][0]){dp[i][j] =  Math.max(dp[i][j],goods[i-1][1]+dp[i-1][j-goods[i-1][0]]);}}}System.out.println(dp[n][v]);// 恰好装满,如果装零个物品,j>=0,那么就装不满,第一行要初始化为-1;for(int j=1;j<=v;j++){dp[0][j] = -1;}for(int i=1;i<=n;i++){for(int j=1;j<=v;j++){// 选第i个物品,且选完第i个物品后恰好装满dp[i][j] = dp[i-1][j];if(j>=goods[i-1][0] && dp[i-1][j-goods[i-1][0]]!=-1){dp[i][j] =  Math.max(dp[i][j],goods[i-1][1]+dp[i-1][j-goods[i-1][0]]);}}}dp[n][v] = dp[n][v]==-1?0:dp[n][v];System.out.println(dp[n][v]);}
}

重难点2：01背包的状态表示

滚动数组做空间上的优化：当我们填写第i行的时候只需要依赖第i-1行的数组，那么就不需要其他行的数据，因此当i行填写完成之后，第i-1行已经没用了，第i+1行的填写只依赖第i行，所以我们可以用第i行覆盖第i-1行。这样进行滚就只需两个数组就可以填冲整个dp表了。如果填写dp[i][j]只依赖dp[i][j’]（j’<j）那么只需一个滚动数组就可以填充整个二维dp表了，要保证的是，在填冲完dp[i][j]之后才能去更新覆盖dp[i][j’]，因此要注意填表顺序。

java">import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();int v = in.nextInt();int[][] goods = new int[n][2];for(int i=0;i<n;i++){goods[i][0] = in.nextInt();goods[i][1] = in.nextInt();}// 求解// int[] dp = new int[v+1];for(int i=1;i<=n;i++){for(int j=v;j>=1;j--){// 不选第i个物品dp[j] = dp[j];// 选第i个物品if(j>=goods[i-1][0]){dp[j] =  Math.max(dp[j],goods[i-1][1]+dp[j-goods[i-1][0]]);}}}System.out.println(dp[v]);// 恰好装满,如果装零个物品,j>=0,那么就装不满,第一行要初始化为-1;for(int j=1;j<=v;j++){dp[j] = -1;}for(int i=1;i<=n;i++){for(int j=v;j>=1;j--){// 选第i个物品,且选完第i个物品后恰好装满dp[j] = dp[j];if(j>=goods[i-1][0] && dp[j-goods[i-1][0]]!=-1){dp[j] =  Math.max(dp[j],goods[i-1][1]+dp[j-goods[i-1][0]]);}}}dp[v] = dp[v]==-1?0:dp[v];System.out.println(dp[v]);}
}// 滚动数组优化空间

leetcode.cn/problems/partition-equal-subset-sum/description/" rel="nofollow">50、分割等和子集

java">class Solution {public boolean canPartition(int[] nums) {int n = nums.length;int sum = 0;for(int i=0;i<n;i++) sum+=nums[i];if(sum%2==1) return false;sum/=2;// sum 相当于背包的容量// 要求正好装满boolean[] dp = new boolean[sum+1];// 初始化,其一行第一列的位置除dp[0][0]都为false;dp[0]=true;// 填表for(int i=1;i<=n;i++){for(int j=sum;j>=1;j--){// 不装入第i个元素,就将背包装满// 要装入第i个元素,且刚好填满if(j>=nums[i-1] &&  dp[j-nums[i-1]]){dp[j] = dp[j-nums[i-1]];}}}return dp[sum];}
}

leetcode.cn/problems/target-sum/description/" rel="nofollow">51、目标和

java">class Solution {public int findTargetSumWays(int[] nums, int target) {// 也是01背包问题,每一个数字都选或者不选target = target>=0?target:-target;int n = nums.length;// dp[i][j]在前i个数构成目标值为j的方式种数// 1000 可以用sum(nums)代替int[][] dp = new int[n+1][1000+1];dp[0][0] = 1;for(int i=1;i<=n;i++){for(int j=0;j<=1000;j++){// 减去if(j+nums[i-1]<=1000){dp[i][j] += dp[i-1][j+nums[i-1]];}// 加上dp[i][j] += dp[i-1][Math.abs(j-nums[i-1])];}}return dp[n][target];}
}
// 空间优化
// 因为需要右上方和左上方的dp[i][j]
// 所以只能优化成dp[2][1001]
/// 题目转化:
// int aim = (sum + target) / 2;
// 子序列和为aim的个数

把问题进行转化，dp简单多了

leetcode.cn/problems/last-stone-weight-ii/description/" rel="nofollow">52、最后一块石头的重量 ★★★★★★ （转化问题的能力）

java">class Solution {public int lastStoneWeightII(int[] stones) {// 好题目// 01背包// 将这一对堆石头分为重量相近的两堆石头// 也就是选一些石头使重量和接近sum/2int n = stones.length;int sum = 0;for(int i=0;i<n;i++) sum+=stones[i];int aim = sum/2;int[] dp = new int[aim+1];for(int i=1;i<=n;i++){for(int j=aim;j>=1;j--){// 不选第i个石头// dp[i][j] = dp[i-1][j]// 选第i个石头if(j-stones[i-1]>=0){dp[j] = Math.max(dp[j],dp[j-stones[i-1]] + stones[i-1]);}}} return sum-2*dp[aim];}
}

这个题目的题意转化很棒
本个题目的难点在于将问题转化为01背包问题

九、完全背包问题

01背包：每一个要么选，要么不选
完全背包：每一个物品无穷多个，都可以选多次或者不选

53、完全背包

java">import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int c = in.nextInt();int[] v = new int[n];int[] w = new int[n];for (int i = 0; i < n; i++) {v[i] = in.nextInt();w[i] = in.nextInt();}// 01背包中每个物品都只有两种可能,要么选要么不选,所以先选那个后选那个并不重要// 完全背包int[][] dp = new int[n + 1][c + 1];// 初始化,如果c==0,则一个物品都拿不了,最大价值只能为0// 如果只能拿0个物品,那么背包容量再大,最大价值也只能是0// 所以扩展出来的第一列和第一行都不需要去初始化,默认为0就好了for (int i = 1; i <= n; i++) {for (int j = 1; j <= c; j++) {// 不装第i个物品dp[i][j] = dp[i - 1][j];if (j - v[i - 1] >= 0) {// 单纯的去想这个状态转移公式会比较难// 通过数学推到的方式可以推导出来// 现有公式再去理解也行dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);}}}System.out.println(dp[n][c]);// 如果要求恰好装满怎么办?// 使用-1约定这个体积凑不出来// 为什么不适用0来约定这个体积凑不出来呢,简单理解:0体积是合理的,不选物品即可即可for(int j=1;j<=c;j++) dp[0][j] = -1; for (int i = 1; i <= n; i++) {for (int j = 1; j <= c; j++) {// 不装第i个物品dp[i][j] = dp[i - 1][j];if (j - v[i - 1] >= 0 && dp[i][j - v[i - 1]]!=-1) {// 单纯的去想这个状态转移公式会比较难// 通过数学推到的方式可以推导出来// 现有公式再去理解也行dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);}}}System.out.println(dp[n][c]==-1?0:dp[n][c]);}
}

java">import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();int c = in.nextInt();int[] v = new int[n];int[] w = new int[n];for (int i = 0; i < n; i++) {v[i] = in.nextInt();w[i] = in.nextInt();}// 01背包中每个物品都只有两种可能,要么选要么不选,所以先选那个后选那个并不重要// 完全背包,int[] dp = new int[c + 1];// 初始化,如果c==0,则一个物品都拿不了,最大价值只能为0// 如果只能拿0个物品,那么背包容量再大,最大价值也只能是0// 所以扩展出来的第一列和第一行都不需要去初始化,默认为0就好了for (int i = 1; i <= n; i++) {for (int j = 1; j <= c; j++) {// 不装第i个物品// dp[i][j] = dp[i - 1][j];if (j - v[i - 1] >= 0) {// 单纯的去想这个状态转移公式会比较难// 通过数学推到的方式可以推导出来// 现有公式再去理解也行dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);}}}System.out.println(dp[c]);// 如果要求恰好装满怎么办?// 使用-1约定这个体积凑不出来// 为什么不适用0来约定这个体积凑不出来呢,简单理解:0体积是合理的,不选物品即可即可for(int j=1;j<=c;j++) dp[j] = -1; for (int i = 1; i <= n; i++) {for (int j = 1; j <= c; j++) {// 不装第i个物品// dp[i][j] = dp[i - 1][j];if (j - v[i - 1] >= 0 && dp[j - v[i - 1]]!=-1) {// 单纯的去想这个状态转移公式会比较难// 通过数学推到的方式可以推导出来// 现有公式再去理解也行dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);}}}System.out.println(dp[c]==-1?0:dp[c]);}
}
// 观察填表顺序，利用滚动数组,进行空间优化
// 每次填充dp[i[j]需要左侧及正上方的dp值,所以可以优化成一维的dp表,填写时从左向右写

java">import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();int c = in.nextInt();int[] v = new int[n];int[] w = new int[n];for (int i = 0; i < n; i++) {v[i] = in.nextInt();w[i] = in.nextInt();}// 01背包中每个物品都只有两种可能,要么选要么不选,所以先选那个后选那个并不重要// 完全背包,int[] dp = new int[c + 1];// 初始化,如果c==0,则一个物品都拿不了,最大价值只能为0// 如果只能拿0个物品,那么背包容量再大,最大价值也只能是0// 所以扩展出来的第一列和第一行都不需要去初始化,默认为0就好了for (int i = 1; i <= n; i++) {for (int j = v[i - 1]; j <= c; j++) {// 不装第i个物品// dp[i][j] = dp[i - 1][j];// 单纯的去想这个状态转移公式会比较难// 通过数学推到的方式可以推导出来// 现有公式再去理解也行dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);}}System.out.println(dp[c]);// 如果要求恰好装满怎么办?// 使用-1约定这个体积凑不出来// 为什么不适用0来约定这个体积凑不出来呢,简单理解:0体积是合理的,不选物品即可即可for(int j=1;j<=c;j++) dp[j] = -1; for (int i = 1; i <= n; i++) {for (int j = v[i-1]; j <= c; j++) {// 不装第i个物品// dp[i][j] = dp[i - 1][j];if (dp[j - v[i - 1]]!=-1) {// 单纯的去想这个状态转移公式会比较难// 通过数学推到的方式可以推导出来// 现有公式再去理解也行dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + w[i - 1]);}}}System.out.println(dp[c]==-1?0:dp[c]);}
}
// 因为填表时要防止数组越界，填表时加一层if判断即可
// 观察代码可以发现，遍历时不去遍历越界的位置，那么在循环体内就省去了if判断的代码

leetcode.cn/problems/coin-change/description/" rel="nofollow">54、零钱兑换

java">class Solution {public int coinChange(int[] coins, int amount) {// 给每种硬币都绑定一个1// coins = [1, 2, 5], amount = 11// 只有 [1,5,5]公用三枚硬币,总和为3最小.然后返回3.int n = coins.length;int[] dp = new int[amount+1];for(int j=1;j<=amount;j++) dp[j] = 0x3f3f3f;for(int i=1;i<=n;i++){for(int j=1;j<=amount;j++){if(j-coins[i-1]>=0 && dp[j-coins[i-1]]!=-1){dp[j] = Math.min(dp[j],dp[j-coins[i-1]]+1);}}}return dp[amount]==0x3f3f3f?-1:dp[amount];}
}

恰好填满的完全背包问题，如果填不满就用-1标记而不是用0标记，之所以这样干你可以理解为编码需要或者0是有意义的，代表用0个硬币就可以填满大小为0的背包。若没有方法可以填满大于0的背包是的方法数不应该为0，而是用-1标记为无法实现。

leetcode.cn/problems/coin-change-ii/" rel="nofollow">55、零钱兑换||

java">class Solution {public int change(int amount, int[] coins) {// 与上一题问法不一样int n = coins.length;// dp[i][j]前i种硬币组成总额为j的方式数目int[][] dp = new int[n+1][amount+1];// 初始化// 第一行表示一个硬币也让不能拿,但是总额大于0,所以dp[0][j]=0// 第一列表示总额为0,可以拿的硬币有很多种,一个也不拿总额就是0了,所以dp[i][0]=1;for(int i=0;i<=n;i++) dp[i][0]=1; for(int i=1;i<=n;i++){for(int j=1;j<=amount;j++){dp[i][j] = dp[i-1][j];if(j-coins[i-1]>=0){dp[i][j] += dp[i][j-coins[i-1]];}}}return dp[n][amount];}
}
// 这是一个常规的完全背包问题的解法

java">class Solution {public int change(int amount, int[] coins) {int n = coins.length;int[] dp = new int[amount+1];for(int i=0;i<=n;i++) dp[0]=1; for(int i=1;i<=n;i++){for(int j=1;j<=amount;j++){if(j-coins[i-1]>=0){dp[j] += dp[j-coins[i-1]];}}}return dp[amount];}
}
// 利用滚动数组做空间上的优化

java">class Solution {public int change(int amount, int[] coins) {int n = coins.length;int[] dp = new int[amount+1];dp[0]=1; for(int i=1;i<=n;i++){//  如果j的起点为coins[i-1]而不是1,当j<coins[i-1]时,dp[i][j]的值为0,然而dp[i][j]的初始值就是0,因此这一部分dp位置不填也可以for(int j=coins[i-1];j<=amount;j++){dp[j] += dp[j-coins[i-1]];}}return dp[amount];}
}// 小优化：填表时不能越界访问，修改遍历范围将j从coins[i-1]开始遍历而不是从1开始。

leetcode.cn/problems/perfect-squares/" rel="nofollow">56、完全平方数

java">class Solution {public int numSquares(int n) {// 最差情况:1+1+1+.......+1+1=n if(n==1) return 1;int m = n/2;int[] dp = new int[n+1];for(int j=1;j<=n;j++){dp[j]=Integer.MAX_VALUE;}for(int i=1;i<=m;i++){// 小优化:将j=1,改为j=i*ifor(int j=i*i;j<=n;j++){dp[j] = Math.min(dp[j],dp[j-i*i]+1);}}return dp[n];}
}

一步步优化
这个问题本质之上是完全背包问题，每一个平方数都可以不选或选多次，并将背包恰好填满，因为最差情况为用1填满，所以不存在背包填不满的情况。
数学上的小优化，因为 (m/2)2 >= m 所以数组规模可以建成[n/2][n]的甚至[n1/2][n]。

十、二维费用的背包问题.

leetcode.cn/problems/ones-and-zeroes/description/" rel="nofollow">57、一和零

java">class Solution {public int findMaxForm(String[] strs, int m, int n) {// 将一些01序列放入背包中,但是背包最多容纳m个1,n个0// 问最多可以装多少个01序列// 二维费用的01背包// 二维费用的完全背包int[][] dp = new int[m+1][n+1];for(String str:strs){int[] temp = fun(str);for(int j=m;j>=temp[0];j--){for(int k=n;k>=temp[1];k--){dp[j][k]  = Math.max(dp[j][k],dp[j-temp[0]][k-temp[1]]+1);}}}return dp[m][n];}public int[] fun(String str){int a = 0;for(char ch : str.toCharArray()) a+=ch-'0';return new int[]{str.length()-a,a};}
}

这是空间优化后的版本，不太那么容易读懂。

leetcode.cn/problems/profitable-schemes/description/" rel="nofollow">58、盈利计划

java">class Solution {public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {int MOD = 1000000007;int m  = group.length;int[][] dp = new int[n+1][minProfit+1];for(int j=0;j<=n;j++) dp[j][0] = 1;for(int i=1;i<=m;i++){ // 任务的数量for(int j=n;j>=group[i-1];j--){ // 员工的数量  为什么是从0开始????for(int k=minProfit;k>=0;k--){ // 最小盈利// 此处小细节dp[j][k] += dp[j-group[i-1]][Math.max(0,k-profit[i-1])];    dp[j][k]%=MOD;    }}}return dp[n][minProfit];}
}
// 1,如何初始化
// 2,填表的范围

背包问题汇总：

费用维度：一维费用背包问题、二位费用背包问题
选取限制：01背包、完全背包
是否恰好装满：背包可容纳的最大价值、恰好装满时的最大价

可见背包问题可以有222=8中形式。

一切的基础都是一维费用的01背包

leetcode.cn/problems/combination-sum-iv/" rel="nofollow">59、似包非包排列总和IV

java">class Solution {// 如果顺序不同也视同一种组合,那么就可以使用完全背包去解决了// 递归解法public int combinationSum4(int[] nums,int target){int ret = 0;int n = nums.length;for(int i=0;i<n;i++){if(target>nums[i])ret+=combinationSum4(nums,target-nums[i]);else if(target==nums[i])ret+=1;}return ret;}
}class Solution {public int combinationSum4(int[] nums,int target){// 将递归转化为动态规划int n = nums.length;int[] dp = new int[target+1];dp[0]=1;for(int i=1;i<=target;i++){for(int j=0;j<n;j++){if(i>nums[j])dp[i]+=dp[i-nums[j]];else if(i==nums[j])dp[i]+=1;}}return dp[target];}
}

我真是个天才

leetcode.cn/problems/unique-binary-search-trees/description/" rel="nofollow">60、卡特兰数不同的二叉搜索树

java">// 递归写法
class Solution {public int numTrees(int n) {// if(n<1) return 1; // 如果这样写就会多递归就有可能会栈溢出if(n<=1) return 1;int ret = 0;for(int i=1;i<=n;i++){ret+=numTrees(i-1)*numTrees(n-i);}return ret;}
}// 动态规划
class Solution {public int numTrees(int n) {int[] dp = new int[n+1];dp[0] = dp[1] = 1;for(int i=2;i<=n;i++){ // 填表dp[i]for(int j=1;j<=i;j++){ // 第j个结点当根节点dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}
}
// 我简直是太厉害了

递归是解决一些复杂问题的有效方法,特别是那些可以分解为更小的子问题的问题。
动态规划填表的过程也是利用了子问题的解进行填表，也就是说一些使用递归方法解决的问题可以转化为动态规划问题：

递归和动态规划都是解决复杂问题的重要编程技术,它们之间有着密切的联系:

分治思想:
- 递归和动态规划都采用分治的思想,将一个复杂的问题分解为更小的子问题。
- 递归通过自身调用来解决子问题,而动态规划则通过存储子问题的结果来避免重复计算。
重叠子问题:
- 许多递归算法会产生大量重复的子问题,这会导致时间复杂度增加。
- 动态规划通过记忆化存储子问题的解来避免重复计算,提高了算法的效率。
最优子结构:
- 动态规划要求问题具有最优子结构,即全局最优解可以由局部最优解组合而成。
- 递归算法也隐含了这种最优子结构的特点,可以通过递归求解子问题来获得最终结果。
实现方式:
- 递归算法通常使用函数调用栈来保存子问题的中间结果。
- 动态规划则通常使用一个存储子问题解的数组/表格来保存中间结果。

总之,递归和动态规划都是重要的算法设计技术,它们在解决复杂问题时往往相互结合使用。动态规划可以优化递归算法,而递归也为动态规划提供了思路和框架。掌握这两种技术对于提高算法设计能力非常重要。