【leetcode刷题记录】（java）动态规划

技术文档

文章目录

一、动态规划
- [509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/)
- - 状态压缩之后的：
  - 没有压缩
- [70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/)
- - 代码
- [746. 使用最小花费爬楼梯](https://leetcode.cn/problems/min-cost-climbing-stairs/)
- [62. 不同路径](https://leetcode.cn/problems/unique-paths/)
- - 代码
- [63. 不同路径 II](https://leetcode.cn/problems/unique-paths-ii/description/)
- - 代码
- [343. 整数拆分](https://leetcode.cn/problems/integer-break/description/)
- - 代码
- [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/description/)
- - Code
二、背包问题（动态规划）
- 01背包
- - 二维数组
  - - 1、dp数组定义状态转移方程
    - 2、初始化
    - 3、代码
  - 一维数组（滚动数组）
  - - 1、dp数组定义状态转移方程
    - 2、初始化
    - 3、代码
- [416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/)
- - 代码
- [1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)
- - code
- [494. 目标和](https://leetcode.cn/problems/target-sum/)
- - 思路
  - dp数组含义、递推公式、初始化
- 二维数组
- 一维数组滚动数组
- - Code
- [474. 一和零](https://leetcode.cn/problems/ones-and-zeroes/description/)
- 思路
- - code
三、完全背包
- 二维数组形式：
- 一维数组：
区分01背包和完全背包（二维数组）
手推：区分01背包和完全背包（一维数组）
- - 01背包
  - 完全背包
[518. 零钱兑换 II](https://leetcode.cn/problems/coin-change-ii/description/)
- 二维数组
- - Code
- 一维数组
四、拓展：完全背包问题，双层循环的顺序，求组合还是求排列数？
- 先遍历物品，内层正序，求组合数
- 先遍历容量，内层正序，求排列数
- 原理解释
- - 当不涉及组合排列的时候建议先遍历物品
- [377. 组合总和 Ⅳ](https://leetcode.cn/problems/combination-sum-iv/)
- [322. 零钱兑换](https://leetcode.cn/problems/coin-change/)
- - code
  - 疑问：直观理解 **dp[j]：凑足总额为j所需钱币的最少个数为dp[j]**
- 代码或者：
- [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)
- - code 完全背包
- [139. 单词拆分](https://leetcode.cn/problems/word-break/)
- - code
- [198. 打家劫舍](https://leetcode.cn/problems/house-robber/)
- - code
- [213. 打家劫舍 II](https://leetcode.cn/problems/house-robber-ii/)
- - code
- (巧妙)[337. 打家劫舍 III](https://leetcode.cn/problems/house-robber-iii/)
- - code
- [121. 买卖股票的最佳时机](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/)（**一股** 股票，1次买卖）
- - 贪心 code
  - 动态规划 code
- [122. 买卖股票的最佳时机 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/) （**一股** 股票，多次买卖）
- - code
- [123. 买卖股票的最佳时机 III](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/) （**一股** 股票，2次买卖）
- - code
- [188. 买卖股票的最佳时机 IV](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/) （**一股** 股票，k次买卖）
- - code
  - - 初始化
- [309. 买卖股票的最佳时机含冷冻期](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/) (多次交易)
- - code
- [714. 买卖股票的最佳时机含手续费](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
- - code
- [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/)
- - code
- [674. （注意体会）最长连续递增序列](https://leetcode.cn/problems/longest-continuous-increasing-subsequence/)
- - code**动态规划**
  - **code 暴力**
- [718（回看）. 最长重复子数组](https://leetcode.cn/problems/maximum-length-of-repeated-subarray/)
- - code
  - code 暴力
- [1143. 最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/description/)
- - Code 复杂的边界初始化
  - code
- [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/)
- - code
  - **Code 动态规划**
- [115. 不同的子序列](https://leetcode.cn/problems/distinct-subsequences/)
- - code
- [516. 最长回文子序列](https://leetcode.cn/problems/longest-palindromic-subsequence/)
- - code
其他
- [740. 删除并获得点数](https://leetcode.cn/problems/delete-and-earn/)
- - code
- [712. 两个字符串的最小ASCII删除和](https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/)
- - code
- [673. 最长递增子序列的个数](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/)
- - code
- [1218. 最长定差子序列](https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/)(已知公差)
- - code 一维数组动态规划双层循环
  - code hashmap 优化
- [1027. 最长等差数列](https://leetcode.cn/problems/longest-arithmetic-subsequence/)（怎么处理不知道的公差?）
- - code 怎么处理不知道的公差?

一、动态规划

动规的五部曲：

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

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4输出：3解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

https://leetcode.cn/problems/fibonacci-number/solutions/2361746/509-fei-bo-na-qi-shu-dong-tai-gui-hua-qi-so8h/

状态压缩之后的：

【leetcode刷题记录】（java）动态规划

class Solution { public int fib(int n) { int a=0,b=1,sum; for(int i=0;i<n;i++){ sum=a+b; a=b; b=sum; } return a; }}

没有压缩

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]; }}

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

示例 2：

输入：n = 3输出：3解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

提示：

1 <= n <= 45

代码

https://leetcode.cn/problems/climbing-stairs/solutions/2361764/70-pa-lou-ti-dong-tai-gui-hua-qing-xi-tu-ruwa/

class Solution { 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<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; }}

746. 使用最小花费爬楼梯

https://leetcode.cn/problems/min-cost-climbing-stairs/solutions/3078338/746-shi-yong-zui-xiao-hua-fei-pa-lou-ti-7rjr7/

注意顶部是dp[n],不是dp[n-1]
注意：dp[i-1]+cost[i-1]放在一起比较大小
不要单独比较cost[i-1] cost[i-2]，因为dp[i-1] dp[i-2]也是变量

class Solution { public int minCostClimbingStairs(int[] cost) { int n=cost.length; int dp[]=new int[n+1];//达到下标为 i 的台阶的最低花费。 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]; }}

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

【leetcode刷题记录】（java）动态规划

输入：m = 3, n = 7输出：28

示例 2：

输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下

https://leetcode.cn/problems/unique-paths/solutions/3078425/62-bu-tong-lu-jing-by-xinyang6-auq9/

注意：边界上的路径数目都是1 而不是i

【leetcode刷题记录】（java）动态规划

 for(int i=0;i<n;i++){ dp[0][i]=i;//错错错 }

代码

class Solution { public int uniquePaths(int m, int n) { int dp[][]=new int[m][n];//到达 m行，n列 路径数 for(int i=0;i<n;i++){ dp[0][i]=1; } for(int i=0;i<m;i++){ dp[i][0]=1; } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[i][j]=dp[i][j-1]+dp[i-1][j]; } } return dp[m-1][n-1]; }}

63. 不同路径 II

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]输出：2解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]输出：1

1.Java 中的 int 数组在创建时默认会被初始化为 0，因此可以直接使用
2.初始化边界赋值

for(int i=0;i<n && obstacleGrid[0][i]==0;i++){//只有没有障碍的时候 才有路径 其他的全部为0 dp[0][i]=1;}

【leetcode刷题记录】（java）动态规划

3.状态转移

if(obstacleGrid[i][j]==0){//只有没有障碍的时候 才赋值 dp[i][j]=dp[i-1][j]+dp[i][j-1];}

【leetcode刷题记录】（java）动态规划

代码

class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m=obstacleGrid.length; int n=obstacleGrid[0].length; int [][]dp=new int[m][n]; for(int i=0;i<n && obstacleGrid[0][i]==0;i++){//只有没有障碍的时候 才有路径 其他的全部为0 dp[0][i]=1; } for(int i=0;i<m && obstacleGrid[i][0]==0;i++){ dp[i][0]=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];  } } } return dp[m-1][n-1];//不可能0行 或者 0列 }}

343. 整数拆分

在 343. 整数拆分问题中，n - i 表示将整数 n 拆分成 i 和 n - i 后，n - i 本身的值，而 F(n - i) 表示将 n - i 继续拆分后得到的最大乘积。

在某些情况下，n - i 的值可能比 F(n - i) 更大，这意味着不继续拆分 n - i 会得到更大的乘积。以下是具体解释和示例：

n - i 较小：
- 当 n - i 较小时（例如 n - i = 2 或 n - i = 3），继续拆分 n - i 反而会减小乘积。
- 例如：
  - 对于 n - i = 2，F(2) = 1（拆分成 1 + 1），但 2 本身比 1 更大。
  - 对于 n - i = 3，F(3) = 2（拆分成 1 + 2），但 3 本身比 2 更大。
n - i 较大：
- 当 n - i 较大时（例如 n - i >= 4），继续拆分 n - i 通常会得到更大的乘积。
- 例如：
  - 对于 n - i = 4，F(4) = 4（拆分成 2 + 2），与 4 本身相等。
  - 对于 n - i = 5，F(5) = 6（拆分成 2 + 3），比 5 本身更大。

乘以2 和乘以（1x1）前者更大

循环遍历的时候上述的n - i 就是 i-j

代码

class Solution { public int integerBreak(int n) { if(n==2)return 1; if(n==3)return 2; //dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。 int dp[]=new int[n+1]; dp[2]=1; dp[3]=2; for(int i=4;i<=n;i++){ for(int j=1;j<i;j++){ dp[i]=Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));//注意这里是三者比较 } } return dp[n]; }}

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3输出：5

示例 2：

输入：n = 1输出：1

https://leetcode.cn/problems/unique-binary-search-trees/solutions/6693/hua-jie-suan-fa-96-bu-tong-de-er-cha-sou-suo-shu-b/

@LiuZZ
难点就在于f(i)=G(i−1)∗G(n−i)这个地方。

首先，这个公式翻译一下就是以i为根节点的二叉搜索树的数量等于以i-1的总数的二叉搜索树的数量乘以以n-1的二叉搜索树的数量。
什么意思呢？
意思就是

假设有n==100,i=50，那么就有以50这个数字为根节点的二叉搜索树的数量等于以49为总数的二叉搜索树的数量乘以以50为总数的二叉搜索树的数量。注意，此时50和49和50，三个数字代表的是不同的意义，第一个50是根节点，第二个49是总数，第三个50还是总数。

想象一下，50这个数字的左边，很明显仅能够从1到49这49个数字进行挑选，这很好理解，因为二叉搜索树的左子树的所有值都必须小于根节点，它们继续在50的左子树下面排列组合，得出的最终各种排列的总数就是G(49)。重点在后面，在50这个数字的根节点的右边，很显然只能是51到100，这50个数字进行排列组合，此时很多人不理解，为什么51到100的排列组合的总数等于G(50)，G(50)从字面意义上看，也就是从0到50的排列组合的总数。

其实道理很简单，将51到100这些数字排列组合的总数，是等于从0到50的排列组合的总数的，因为将51替换为1，将52替换为2，以此类推下去，将100替换为50，就很容易理解了，因为本质上就是50个从大到小的不同的数进行二叉树的排列组合，不论是1001到1050，还是从51到100，所排列组合的二叉树数量是一样的。

所以，这也就解释了这个公式为什么是f(50) = G(49) * G(50)，因为在50这个根节点的左边，有1到49这些数字在不断进行排列组合得出总的排列组合数，在50的右边，有51到100这些数字同样的在不断的进行排列组合得出总的排列组合数，自然而然的，50作为根节点时，所能得到的不同组合，就是G(49) * G(50)了。

【leetcode刷题记录】（java）动态规划

Code

class Solution { //1到i为节点组成的二叉搜索树的个数为dp[i]。 //节点总数为i, 除了根节点之外 ，左右子树的节点数目之和为i-1, //设根节点下标可能为j , 左子树节点个数可能为j-1,右子树节点个数可能为i-1-(j-1) =i-j 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=1;j<=i;j++){//总共i个节点，下标j最多达到i int indexj=dp[j-1]*dp[i-j]; dp[i]+=indexj; } } return dp[n]; }}

二、背包问题（动态规划）

【leetcode刷题记录】（java）动态规划

总结：

求组合数：动态规划：518.零钱兑换II (opens new window)

求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包） (opens new window)

求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数(opens new window)

boolean， dp 排列相关：139. 单词拆分

01背包

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

重量价值物品0 1 15 物品1 3 20 物品2 4 30

二维数组

1、dp数组定义状态转移方程

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

不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

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

自己的话理解：

为什么都是i-1, 不放i的时候就是从[0- i-1]的物品里任意取，放i的时候就是从[0- i-1]的物品里任意取的最优价值+物品i的价值

dp[i - 1][j] 容量为 j 的背包不放物品i,所以前面就是i-1

dp[i - 1][j - weight[i]] + value[i] 容量为 j 的背包放物品 i ,“放”体现在“+ value[i]”，

放之前是要在背包里先把物品i的容量空出来：容量为 j - weight[i] 的背包放 0~i-1 的物品,所以前面就是i-1

dp[i - 1][j] ：容量为 j 的背包就是不放物品i

dp[i - 1][j - weight[i]] + value[i] ：容量为 j 的背包已经放了（+ value[i]）物品i,剩下的容量（j - weight[i]）靠谁来凑

2、初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：

【leetcode刷题记录】（java）动态规划

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

【leetcode刷题记录】（java）动态规划

3、代码

int[][] dp = new int[n][bagweight + 1];for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0];}for (int i = 1; i < n; i++) { for (int j = 0; j <= bagweight; j++) { if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } }}

一维数组（滚动数组）

1、dp数组定义状态转移方程

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

【leetcode刷题记录】（java）动态规划

如上图:注意，循环还是双层循环，只是数组降为了一维数组

i从上到下，还是正序

j从右到左，倒序

自己的话理解：

说白了，当前dp[i]要使用上一层左侧的dp值，正序覆盖了上一层左侧的dp值，倒叙避免了覆盖

二维数组利用的是左上和正上方的数据，转换为一维数组，就要利用左边数据，如果正序遍历就会覆盖左边数据，所以得倒着来

内层循环里面有个条件 j >= weight[i]，那么j < weight[i]的时候，不是没有操作，只是没有更新（直接继承了之前的数值）

2、初始化

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

3、代码

先遍历物品重量
内层循环背包容量从后往前循环

// 创建一个动态规划数组 dp，初始值为 0int[] dp = new int[N + 1];for (int i = 0; i < M; i++) {// 遍历物品 for (int j = bagweight; j >= weight[i]; j--) {// 遍历容量 //从后往前循环 dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]); }}

416. 分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。

代码

class Solution { public boolean canPartition(int[] nums) { if(nums == null || nums.length == 0) return false; //dp[j] 表示： 容量（所能装的重量）为j的背包，所背的物品价值最大可以为dp[j]。 //本题中每一个元素的数值既是重量，也是价值 int n=nums.length; 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<n;i++){//遍历 背包里面所有物品的重量 for(int j=target;j>=nums[i];j--){//逆序遍历所有容量 dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]); } if(dp[target]==target){ return true; } } return dp[target]==target; }}

1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]输出：1解释：组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]输出：5

code

【leetcode刷题记录】（java）动态规划

class Solution { public int lastStoneWeightII(int[] stones) { int sum=0,n=stones.length; for(int num:stones){ sum+=num; } int target=sum/2; int dp[]=new int[target+1];//dp[i]容量为i的筐最大能容纳的石头的总重量 //类似01背包 石头的重量就是物品的重量 衡量价值也是使用的物品的重量来衡量 //假设所有石头总重量为sum 那么dp[sum/2] 和 dp[sum-sum/2]的差值就是最后能剩余的最小石头重量 //假设所有石头总重量为23 那么dp[11] 和 dp[12]的差值就是最后能剩余的最小石头重量 // 7 4 2 1 8 1 1 // for(int i=0;i<n;i++){ for(int j=target;j>=stones[i];j--){ dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]); } } return sum-dp[target]-dp[target]; }}

494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 \'+\' 或 \'-\' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 \'+\' ，在 1 之前添加 \'-\' ，然后串联起来得到表达式 \"+2-1\" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 = 3

思路

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

= 通过各个元素 + 还是 - 来凑成target的方法个数

= 只需要知道哪些元素是+号，那么其他元素都是-， +元素为 left组合 ，-元素为 right组合，有 left组合 - right组合 = target。

left + right = sum，而sum是固定的。right = sum - left

left - (sum - left) = target 推导出 left = (target + sum)/2 。

= 问题就是在集合nums中找出和为left的组合

哪些元素选为带上+号，哪些元素不选为带上+号，而且只能选一次，

（不用管哪些元素带上 - 号，+号的元素一旦确定， - 号的元素就确定了）

dp数组含义、递推公式、初始化

dp[i][j]：使用下标为 [0, i] 的 nums[i] 能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

if (nums[i] > j) dp[i][j] = dp[i - 1][j]; //nums[i] 元素已经比容量大，不能刚好凑满jelse dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];//选择nums[i] 不选择nums[i] 方法之和

先明确递推的方向，如图，求解 dp[2][2] 是由上方和左上方推出。

【leetcode刷题记录】（java）动态规划

那么二维数组的最上行和最左列一定要初始化

关于dp[0][0]的值，装满背包容量为0 的方法数量是1，即放0件物品。

二维数组

注意第一列的初始化

class Solution494 { public int findTargetSumWays(int[] nums, int target) { int sum = 0; int n = nums.length; for (int num : nums) { sum += num; } if (sum < Math.abs(target)) { return 0; } int addSum = (sum + target) / 2; if((sum + target) % 2 != 0) {//如果没有恰好的addSum这个数，那么最终也凑不成target return 0; } int dp[][] = new int[n][addSum + 1]; dp[0][0] = 1; if (nums[0] <= addSum) { dp[0][nums[0]] = 1; } int numZeros = 0; for (int i = 0; i < nums.length; i++) {//注意这里的初始化，特别注意数值为0的情况 if (nums[i] == 0) { numZeros++; } dp[i][0] = (int) Math.pow(2, numZeros); } for (int i = 1; i < n; i++) { for (int j = 1; j <= addSum; j++) { } } return dp[n - 1][addSum]; }}

一维数组滚动数组

https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html#%E6%80%9D%E8%B7%AF

关于一维dp数组的递推公式解释，也可以从以下维度来理解。（但还是从二维DP数组到一维DP数组这样更容易理解一些）

确定递推公式
有哪些来源可以推出dp[j]呢？

只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

已经有一个1（nums[i]）的话，有 dp[4]种方法凑成容量为5的背包。
已经有一个2（nums[i]）的话，有 dp[3]种方法凑成容量为5的背包。
已经有一个3（nums[i]）的话，有 dp[2]种方法凑成容量为5的背包
已经有一个4（nums[i]）的话，有 dp[1]种方法凑成容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]种方法凑成容量为5的背包
那么凑整dp[5]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

Code

class Solution { public int findTargetSumWays(int[] nums, int target) { int n = nums.length; int sum = 0; for (int num : nums) { sum += num; } if (sum < Math.abs(target)) { return 0; } if ((sum + target) % 2 != 0) { return 0; } int addSum = (sum + target) / 2; int dp[] = new int[addSum + 1];// 凑成数值为i，可以的方法为dp[i]种 dp[0] = 1; for (int i = 0; i = nums[i]; j--) { dp[j] = dp[j] + dp[j - nums[i]]; } } return dp[addSum]; }}

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = [\"10\", \"0001\", \"111001\", \"1\", \"0\"], m = 5, n = 3输出：4解释：最多有 5 个 0 和 3 个 1 的最大子集是 {\"10\",\"0001\",\"1\",\"0\"} ，因此答案是 4 。其他满足题意但较小的子集包括 {\"0001\",\"1\"} 和 {\"10\",\"1\",\"0\"} 。{\"111001\"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = [\"10\", \"0\", \"1\"], m = 1, n = 1输出：2解释：最大的子集是 {\"0\", \"1\"} ，所以答案是 2 。

思路

这里类似01背包的滚动数组的解法，已经优化了空间
这里不需要初始化第一行和第一列，只需要初始化第一个数据dp[0][0]=0

code

提前统计好每个字符的0和1的个数

class Solution { public int findMaxForm(String[] strs, int m, int n) { int len = strs.length; int[][] strs01cnt = new int[len][2]; for (int k = 0; k < len; k++) {//提前统计好每个字符的0和1的个数 int strlen = strs[k].length(); for (int j = 0; j < strlen; j++) { if (strs[k].charAt(j) == \'0\')  strs01cnt[k][0]++; else {  strs01cnt[k][1]++; } } } int dp[][] = new int[m + 1][n + 1]; for (int k = 0; k = strs01cnt[k][0]; i--) { for (int j = n; j >= strs01cnt[k][1]; j--) {  dp[i][j] = Math.max(dp[i][j], dp[i - strs01cnt[k][0]][j - strs01cnt[k][1]] + 1); } } } return dp[m][n]; }}

每个字符的0和1的个数的统计可以卸写在最外层的循环里面
https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

class Solution { public int findMaxForm(String[] strs, int m, int n) { //dp[i][j]表示i个0和j个1时的最大子集 int[][] dp = new int[m + 1][n + 1]; int oneNum, zeroNum; for (String str : strs) { oneNum = 0; zeroNum = 0; for (char ch : str.toCharArray()) { if (ch == \'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]; }}

三、完全背包

二维数组形式：

不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

（注意，完全背包二维dp数组和 01背包二维dp数组递推公式的区别，01背包中是 dp[i - 1][j - weight[i]] + value[i])）

在 01背包理论基础（二维数组） (opens new window)中，背包先空留出物品1的容量，此时容量为1，只考虑放物品0的最大价值是 dp[0][1]，因为01背包每个物品只有一个，既然空出物品1，那背包中也不会再有物品1！

而在完全背包中，物品是可以放无限个，所以即使空出物品1空间重量，那背包中也可能还有物品1，所以此时我们依然考虑放物品0 和物品1 的最大价值即： dp[1][1]，而不是 dp[0][1]

// 初始化for (int j = weight[0]; j <= bagWeight; j++) { dp[0][j] = dp[0][j - weight[0]] + value[0];}// 动态规划for (int i = 1; i < n; i++) { for (int j = 0; j <= bagWeight; j++) { if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]); } }}

一维数组：

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

区分01背包和完全背包（二维数组）

01背包：

for (int i = 1; i < n; i++) { for (int j = 0; j <= bagweight; j++) { if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } }}

dp[i-1][j - weight[i]] + value[i]

容量为 j 的背包已经放了（+ value[i]）物品i,剩下的容量（j - weight[i]）仅仅靠0~i-1 来凑 （dp[i-1][j - weight[i]]）

完全背包：

// 动态规划for (int i = 1; i < n; i++) { for (int j = 0; j <= bagWeight; j++) { if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]); } }}

dp[i][j - weight[i]] + value[i]

容量为 j 的背包已经放了（+ value[i]）物品i,剩下的容量（j - weight[i]）还是靠0~i 来凑 （dp[i-1][j - weight[i]]）

因为weight[i]有无数个

手推：区分01背包和完全背包（一维数组）

01背包

【leetcode刷题记录】（java）动态规划

完全背包

【leetcode刷题记录】（java）动态规划

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]输出：0解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 输出：1

二维数组

注意初始化第一行，只使用第一个硬币的时候：（题目中说的是恰好凑成），而不是类似背包问题中的最大能够容纳多少硬币

//错误的初始化for (int j = 0; j <= amount; j++) { if (j - coins[0] >= 0) { dp[0][j] += dp[0][j - coins[0]]; } else { dp[0][j] = 1; }}//正确的初始化for (int j = 0; j <= amount; j++) { if (j % coins[0] == 0) { dp[0][j] = 1; // 如果 j 是 coins[0] 的倍数，组合数为 1 } else { dp[0][j] = 0; // 否则为 0 }}

Code

有0~i的硬币，但是容量为0，方法只有一种，不放。dp[i][0]=1;
只有编号为0的硬币，容量为j,但是当j不是此硬币数值的倍数，那么方法为0

class Solution { public int change(int amount, int[] coins) { int n = coins.length; int dp[][] = new int[n][amount + 1]; // 初始化第一行：只使用第一个硬币 for (int j = 0; j <= amount; j++) { if (j % coins[0] == 0) { dp[0][j] = 1; // 如果 j 是 coins[0] 的倍数，组合数为 1 } else { dp[0][j] = 0; // 否则为 0 } } for (int i = 0; i < n; i++) { dp[i][0] = 1; } for (int i = 1; i < n; i++) { for (int j = 0; j <= amount; j++) { if (j < coins[i]) {  dp[i][j] = dp[i - 1][j]; } else {  dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]; } } } return dp[n - 1][amount]; }}

一维数组

class Solution { public int change(int amount, int[] coins) { int dp[]=new int[amount+1]; int n=coins.length; dp[0]=1;//dp[0] 应该初始化为 1，因为凑成金额为 0 的组合只有一种，即不使用任何硬币 for(int i=0;i<n;i++){ for(int j=coins[i];j<=amount;j++){ dp[j]=dp[j]+dp[j-coins[i]]; //dp[j] 应该等于 dp[j] + dp[j - coins[i]]，而不是 dp[j] + dp[j - coins[i]] + coins[i]。 // 因为我们要计算的是组合数，而不是金额的总和。 } } return dp[amount]; }}

四、拓展：完全背包问题，双层循环的顺序，求组合还是求排列数？

先遍历物品，内层正序，求组合数

【leetcode刷题记录】（java）动态规划

先遍历容量，内层正序，求排列数

【leetcode刷题记录】（java）动态规划

原理解释

题目：518. 零钱兑换 II

在完全背包（一维DP）中完全背包的两个for循环的先后顺序都是可以的。因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！

**但本题就不行了！**本题要求凑成总和的组合数，元素之间明确要求没有顺序

本题是求凑出来的方案个数，且每个方案个数是组合数。

那么本题，两个for循环的先后顺序可就有说法了。

我们先来看外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。

代码如下：
for (int i = 0; i < coins.size(); i++) { // 遍历物品 for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量  dp[j] = dp[j] + dp[j - coins[i]]; }}
假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数！

如果把两个for交换顺序，代码如下：
for (int j = 0; j <= amount; j++) { // 遍历背包容量 for (int i = 0; i < coins.size(); i++) { // 遍历物品  if (j - coins[i] >= 0) dp[j] = dp[j] + j - coins[i]]; }}
背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数！

当不涉及组合排列的时候建议先遍历物品

377. 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4输出：7解释：所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。

class Solution { public int combinationSum4(int[] nums, int target) { int n = nums.length; int dp[] = new int[target + 1];// 能组成数字为j 的 组合个数 dp[0] = 1;//1 <= target <= 1000 ,所以dp[0] = 1没有什么实际意义，仅仅是为了推导递推公式。 for (int j = 0; j <= target; j++) {//注意：j 也不能初始化为nums[0] 因为nums[0]也不一定是最小的数 for (int i = 0; i < n; i++) { if (j >= nums[i]) {  dp[j] = dp[j] + dp[j - nums[i]]; } } } return dp[target]; }}

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1

code

class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE; int[] dp = new int[amount + 1]; //初始化dp数组为最大值 //dp[j]：凑足总额为j所需钱币的最少个数为dp[j] for (int j = 0; j < dp.length; j++) { dp[j] = max; } //当金额为0时需要的硬币数目为0 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]; }}

疑问：直观理解 dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

那么 dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);

选硬币coins[i] 和不选硬币coins[i] ,取 Math.min，肯定是“不选硬币coins[i] ” 所需钱币个数最少啊？

AI解释： deepseek真牛逼

比如，假设当前在处理硬币面额2，当前的j是4。那么dp[4]可能已经被之前的硬币（比如1元）计算过是4

dp[4]=4 （四个一元的），共4个硬币

dp[4] = Math.min(dp[4-coins[i]=2] + 1, dp[2]) dp[4]就会被更新为 dp[2]+1=3 两个一元的加一个2元的，共3个硬币

（或者如果dp[2]已经是最优的那么可能是dp[2]=1 ，一个2元的）

这显然比原来的4更优。所以这时候取较小值是正确的。

所以这里的逻辑是，对于每个硬币coins[i]，我们尝试在之前的基础上加上这个硬币，看看是否能得到更优的解。比如，之前的dp[j]可能已经被其他硬币的组合填充过（更小面额的硬币可能需要较多的数量），而当前硬币可能可以用更少的数量来达到同样的金额。

代码或者：

class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE-1;//如果后面不加if判断 这里就-1 因为之后的+1 会导致max溢出变成最小值 int[] dp = new int[amount + 1]; //初始化dp数组为最大值 for (int j = 0; j < dp.length; j++) { dp[j] = max; } //当金额为0时需要的硬币数目为0 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]; }}

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12输出：3 解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13输出：2解释：13 = 4 + 9

code 完全背包

class Solution { public int numSquares(int n) { int max=Integer.MAX_VALUE; int nums[]=new int[101]; for(int i=0;i<=100;i++){ nums[i]=i*i; } int dp[]=new int[n+1]; for(int i=1;i<=n;i++){ dp[i]=max; } dp[0]=0; for(int i=0;i<=100;i++){ for(int j=nums[i];j<=n;j++){ if(dp[j-nums[i]]!=max){  dp[j]=Math.min(dp[j],dp[j-nums[i]]+1); } } } return dp[n]; }}

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = \"leetcode\", wordDict = [\"leet\", \"code\"]输出: true解释: 返回 true 因为 \"leetcode\" 可以由 \"leet\" 和 \"code\" 拼接成。

示例 2：

输入: s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]输出: true解释: 返回 true 因为 \"applepenapple\" 可以由 \"apple\" \"pen\" \"apple\" 拼接成。 注意，你可以重复使用字典中的单词。

示例 3：

输入: s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]输出: false

code

class Solution { public boolean wordBreak(String s, List<String> wordDict) { HashSet<String> set = new HashSet<>(wordDict); //dp[j] : 字符串长度为j的话，dp[j]为true，表示可以拆分为一个或多个在字典中出现的单词。 boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int j = 1; j <= s.length(); j++) {//先遍历容量 //其实物品是substring(i, j)，这里的遍历i相当于模仿遍历物品的过程 for (int i = 0; i < j; i++) {//由于后面的substring 左闭右开 ，所里这里i<j 不是<= if (set.contains(s.substring(i, j)) && dp[i]) {  dp[j] = true; } } } return dp[s.length()]; }}

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

code

class Solution { public int rob(int[] nums) { int n=nums.length; if(n==1)return nums[0]; int dp[]=new int[n];//使用下标为0~i的元素 所能凑成的最大数 dp[0]=nums[0]; dp[1]=Math.max(nums[0],nums[1]); for(int i=2;i<n;i++){ dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]); //选nums[i] ，那么nums[i-1]不选，之前的状态：使用下标为0~i-2的元素 所能凑成的最大数 //不选nums[i],即只考虑0~i-1房凑成的最大数 } return dp[n-1]; }}

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]输出：3解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]输出：4解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。

code

class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; if (n == 2) return Math.max(nums[0], nums[1]); return Math.max(findmax(nums, 0, n - 2), findmax(nums, 1, n - 1)); } public int findmax(int[] nums, int start, int end) { int dp[] = new int[nums.length];// 使用下标为0~i的元素 所能凑成的最大数 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]); // 选nums[i] ，那么nums[i-1]不选，之前的状态：使用下标为0~i-2的元素 所能凑成的最大数 // 不选nums[i],即只考虑0~i-1房凑成的最大数 } return dp[end];// 使用下标为0~i的元素 所能凑成的最大数，可以使用的最大下标就是end }}

(巧妙)337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额

示例 1:

输入: root = [3,2,3,null,3,null,1]输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

code

class Solution { public int rob(TreeNode root) { int []res=postOrder(root); return Math.max(res[0],res[1]); } private int []postOrder(TreeNode root){ int []cur=new int[2]; if(root==null){ return cur; } int []left=postOrder(root.left); int []right=postOrder(root.right); cur[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]); cur[1]= root.val+left[0]+right[0]; return cur; }}

如果是偷当前节点，那么左右孩子就不能偷，cur[1]= root.val+left[0]+right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：cur[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);

121. 买卖股票的最佳时机（一股股票，1次买卖）

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

贪心 code

class Solution { public int maxProfit(int[] prices) { //当前遍历到的prices[i] 减去 “之前遍历的所有数的最小值” int n=prices.length; int res=0; int min=Integer.MAX_VALUE; for(int i=0;i<n;i++){ min=Math.min(min,prices[i]); res=Math.max(res,prices[i]-min); } return res; }}

动态规划 code

dp[i][1] 表示第i天持有股票所得最多现金

注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态
很多同学把“持有”和“买入”没区分清楚。

【leetcode刷题记录】（java）动态规划

class Solution { public int maxProfit(int[] prices) { int n=prices.length; int dp[][]=new int[n][2]; dp[0][0]=0; dp[0][1]=-prices[0]; for(int i=1;i<n;i++){ dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); dp[i][1]=Math.max(dp[i-1][1],-prices[i]); } return dp[n-1][0]; }}

解释：

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);//今天手上没有股票= 昨天就没有 或者 “昨天就有了（可能是在昨天或者昨天之前买的） ，今天卖了”dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);//今天手上有股票=“昨天就有了 （还没卖）” 或者 今天刚买

122. 买卖股票的最佳时机 II （一股股票，多次买卖）

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]输出：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。最大总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。最大总利润为 4 。

code

dp[i][0] 表示第i天 不持有 股票所得现金。
dp[i][1] 表示第i天持有股票所得最多现金

class Solution { public int maxProfit(int[] prices) { int n=prices.length; int dp[][]=new int[n][2]; dp[0][0]=0; dp[0][1]=-prices[0]; for(int i=1;i<n;i++){ dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); //今天手上没有股票= 昨天就没有 或者 “昨天就有了（可能是在昨天或者昨天之前买的） ，今天卖了” dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); //今天手上有股票=“昨天就有了 （还没卖）”  // 或者  // dp[i-1][0]-prices[i] （昨天没有 （可能是昨天之前买的，在昨天或昨天之前卖了））,今天刚买  //体现的是可以重复购买 } return dp[n-1][0]; }}

123. 买卖股票的最佳时机 III （一股股票，2次买卖）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]输出：6解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]输出：4解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

code

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html#%E6%80%9D%E8%B7%A

class Solution { public int maxProfit(int[] prices) { int n = prices.length; int dp[][] = new int[n][5]; dp[0][1] = -prices[0]; dp[0][3] = -prices[0];//注意这里的初始化 // 第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？ // 第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了， // 然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。 // 所以第二次买入操作，初始化为：dp[0][3] = -prices[0]; for (int i = 1; i < n; 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[n - 1][4]; }}

【leetcode刷题记录】（java）动态规划

如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。

188. 买卖股票的最佳时机 IV （一股股票，k次买卖）

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]输出：2解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]输出：7解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

code

https://programmercarl.com/0188.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIV.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

class Solution { public int maxProfit(int k, int[] prices) { int n=prices.length; int dp[][]=new int[n][k*2+1]; for(int j=0;j<k*2+1;j++){ if(j%2==1){ dp[0][j]=-prices[0]; } } for(int i=1;i<n;i++){ for(int j=1;j<k*2+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[n-1][2*k]; }}

初始化

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，这个初始值应该是多少呢？

此时还没有买入，怎么就卖出呢？其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;

第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？

第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后在买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。

所以第二次买入操作，初始化为：dp[0][3] = -prices[0];

第二次卖出初始化dp[0][4] = 0;

所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]

【leetcode刷题记录】（java）动态规划

309. 买卖股票的最佳时机含冷冻期 (多次交易)

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]输出: 0

code

class Solution { public int maxProfit(int[] prices) { int n = prices.length; if(n==1)return 0; int dp[][] = new int[n][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; dp[1][0] = Math.max(0,prices[1]-prices[0]);//没有操作 或者 “第0天买 第1天卖” dp[1][1] = Math.max(-prices[1],-prices[0]);//第0天买 或者 第1天买 for (int i = 2; i < n; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 今天手上没有股票= 昨天就没有 或者 “昨天就有了（可能是在昨天或者昨天之前买的） ，今天卖了” dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]); // 今天手上有股票=“昨天就有了 （还没卖）” // 或者 // dp[i-2][0]-prices[i] （前天没有 （可能是前天之前买的，在前天或前天之前卖了））,今天刚买 //注意：昨天手中没有股票 不能推出 今天买了，因为冻结（可能昨天刚卖） // 体现的是可以重复购买 } return dp[n - 1][0]; }}

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

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2输出：8解释：能够达到的最大利润: 在此处买入 prices[0] = 1在此处卖出 prices[3] = 8在此处买入 prices[4] = 4在此处卖出 prices[5] = 9总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3输出：6

code

卖出的时候减去手续费
注意：这个手续费不能在买入的时候扣，不然只能通过部分样例，我也不知道为啥

class Solution { public int maxProfit(int[] prices, int fee) { int n = prices.length; int dp[][] = new int[n][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; 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]); // 今天手上有股票=“昨天就有了 （还没卖）” // 或者 // dp[i-1][0]-prices[i] （昨天没有 （可能是昨天之前买的，在昨天或昨天之前卖了））,今天刚买 // 体现的是可以重复购买 } // return Math.max(dp[n - 1][0], dp[n - 1][1]); return dp[n - 1][0]; }}

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]输出：4

示例 3：

输入：nums = [7

code

class Solution { public int lengthOfLIS(int[] nums) { int n=nums.length; int dp[]=new int[n];//dp[i]表示 i以及i之前 以nums[i]结尾的最长递增子序列的长度 Arrays.fill(dp, 1); int res=1;q for(int j=1;j<n;j++){ for(int i=0;i<j;i++){ if(nums[j]>nums[i]){  dp[j]=Math.max(dp[j],dp[i]+1);  //注意这里不是要dp[j] 与 dp[i] + 1进行比较，而是要取dp[i] + 1的最大值。  //dp[j]多次被 dp[i]+1 赋值，需要取 dp[i]+1 的最大值 } } res=Math.max(res,dp[j]); } return res;//最终的最大值 子序列不一定以最后一个数结尾 所以不返回dp[n-1] }}

【leetcode刷题记录】（java）动态规划

674. （注意体会）最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]输出：3解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

输入：nums = [2,2,2,2,2]输出：1解释：最长连续递增序列是 [2], 长度为1。

code动态规划

class Solution { public int findLengthOfLCIS(int[] nums) { int n=nums.length; int dp[]=new int [n]; int res=1; Arrays.fill(dp,1); for(int i=1;i<n;i++){ if(nums[i-1]<nums[i]){//没有进入此判断的dp[i]依旧是默认值1 dp[i]=dp[i-1]+1; res=Math.max(res,dp[i]);//只有dp[i]更新了，采取更新最大值res；比放在if外面效率高 } } return res; }}

code 暴力

class Solution { public int findLengthOfLCIS(int[] nums) { int n=nums.length; int res=1; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(nums[j-1]>=nums[j]){  break; } res=Math.max(res,j-i+1); } } return res; }}

718（回看）. 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]输出：3解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]输出：5

code

令dp(i,j)为nums1前i个元素，与nums2前j个元素的「最长公共子数组」长度，注意参数的意义，这里是个数，所以dp*(m,n)是最后一个，dp数组长度要加1。

那么，状态f(i,j)的全局最值就是问题的解。

因为子数组必须要连续，所以如果当前元素相等，那么从前一个长度加1，否则就是0：
【leetcode刷题记录】（java）动态规划

class Solution { public int findLength(int[] nums1, int[] nums2) { // 获取两个数组的长度 int m = nums1.length; int n = nums2.length; // 创建一个二维数组 dp，用于存储最长公共子数组的长度 int[][] dp = new int[m + 1][n + 1];//dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。  // 初始化最大长度为 0 int max = 0; // 遍历 nums1 的每个元素（从 1 到 m） for (int i = 1; i < =m ; i++) { // 遍历 nums2 的每个元素（从 1 到 n） for (int j = 1; j < =n ; j++) { // 如果当前元素相等 if (nums1[i - 1] == nums2[j - 1]) {  //此时nums1长度为i、nums2长度为j，dp[i][j]表示二者公共子串的最大长度  dp[i][j] = dp[i - 1][j - 1] + 1;  // 更新最大长度  max = Integer.max(max, dp[i][j]); } } } // 返回最大长度 return max; }}

code 暴力

只需要先两层for循环确定两个数组起始位置，然后再来一个循环可以是for或者while，来从两个起始位置开始比较，取得重复子数组的长度。

class Solution { public int findLength(int[] nums1, int[] nums2) { int maxlen=0; for(int i=0;i<nums1.length;i++){ for(int j=0;j<nums2.length;j++){ if( nums1[i]==nums2[j]){  int end1=i+1,end2=j+1;  while(end1<nums1.length && end2<nums2.length && nums1[end1]==nums2[end2]){ end1++; end2++;  }  maxlen=Math.max(maxlen,end1-i); } } } return maxlen; }}

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，\"ace\" 是 \"abcde\" 的子序列，但 \"aec\" 不是 \"abcde\" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = \"abcde\", text2 = \"ace\" 输出：3 解释：最长公共子序列是 \"ace\" ，它的长度为 3 。

示例 2：

输入：text1 = \"abc\", text2 = \"abc\"输出：3解释：最长公共子序列是 \"abc\" ，它的长度为 3 。

Code 复杂的边界初始化

i和j是下标
dp[i][j] 表示 text1 的以下标i结尾的字符（text1前i+1个）和 text2 的以下标j结尾的字符（text2前j+1个）的最长公共子序列的长度。

class Solution { public int longestCommonSubsequence(String text1, String text2) { int len1=text1.length(); int len2=text2.length(); if(len1==0 || len2==0)return 0; int dp[][]=new int [len1][len2]; if(text1.charAt(0)==text2.charAt(0)){ dp[0][0]=1; } //初始化第一行 for(int j=1;j<len2;j++){ if(text2.charAt(j)==text1.charAt(0)){ dp[0][j]=1; } else if(dp[0][j-1]==1) { dp[0][j]=1; }else{ dp[0][j]=0; } } //初始化第一列 for(int i=1;i<len1;i++){ if(text1.charAt(i)==text2.charAt(0)){ dp[i][0]=1; } else if(dp[i-1][0]==1) { dp[i][0]=1; }else{ dp[i][0]=0; } } for(int i=1;i<len1;i++){ for(int j=1;j<len2;j++){ if(text1.charAt(i)==text2.charAt(j)){  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[len1-1][len2-1]; }}

i和j是长度
dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
相比较于上面的代码，相当于初始化写在了两层for循环里面

code

class Solution { public int longestCommonSubsequence(String text1, String text2) { int len1 = text1.length(); int len2 = text2.length(); if (len1 == 0 || len2 == 0) return 0; // 创建 (len1 + 1) * (len2 + 1) 的 dp 数组 int[][] dp = new int[len1 + 1][len2 + 1]; // 填充 dp 数组 for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; 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[len1][len2]; }}

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]输出：1

示例 3：

输入：nums = [5,4,-1,7,8]输出：23

code

Code 动态规划

class Solution { public int maxSubArray(int[] nums) { int n=nums.length; if(n==1)return nums[0]; int dp[]=new int[n+1];//dp[i]表示以nums[i]结尾的数组 的 最大子数组和 dp[0]=nums[0]; int max=dp[0];//注意这里不能初始化为MIN_VALUE for(int i=1;i0){ dp[i]=dp[i-1]+nums[i];////无论nums[i]大于或者小于0 加上dp[i-1]会变大 } else{ dp[i]=nums[i];//无论nums[i]大于或者小于0 加上dp[i-1]只会更小 } max=Math.max(dp[i],max); } return max; }}

code 前缀和超时

class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] sum = new int[n + 1]; for (int i = 0; i < n; i++) { sum[i + 1] = sum[i] + nums[i]; } int max = Integer.MIN_VALUE; for (int l = 0; l < n; l++) { for (int r = l + 1; r <= n; r++) { max = Math.max(max, sum[r] - sum[l]); } } return max; }}

【leetcode刷题记录】（java）动态规划

115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = \"rabbbit\", t = \"rabbit\"输出：3解释：如下所示, 有 3 种可以从 s 中得到 \"rabbit\" 的方案。rabbbitrabbbitrabbbit

示例 2：

输入：s = \"babgbag\", t = \"bag\"输出：5解释：如下所示, 有 5 种可以从 s 中得到 \"bag\" 的方案。 babgbagbabgbagbabgbagbabgbagbabgbag

code

https://leetcode.cn/problems/distinct-subsequences/solutions/3060706/jiao-ni-yi-bu-bu-si-kao-dpcong-ji-yi-hua-9va6/

【leetcode刷题记录】（java）动态规划

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

【leetcode刷题记录】（java）动态规划

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = \"bbbab\"输出：4解释：一个可能的最长回文子序列为 \"bbbb\" 。

示例 2：

输入：s = \"cbbd\"输出：2解释：一个可能的最长回文子序列为 \"bb\" 。

code

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

注意：根据定义需要初始化dp[i][i]=1;

【leetcode刷题记录】（java）动态规划

class Solution { public int longestPalindromeSubseq(String s) { char ch[]=s.toCharArray(); int [][]dp=new int[ch.length][ch.length]; for(int i=0;i<ch.length;i++){ dp[i][i]=1; } for(int i=ch.length-1;i>=0;i--){ for(int j=i+1;j<ch.length;j++){//注意这里是i+1 因为i==j的情况已经在初始化中给出，这里保证j!=i 不是相同的字符 if(ch[i]==ch[j]){  dp[i][j]=dp[i+1][j-1]+2; }else{  dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]); } } } return dp[0][ch.length-1]; }}

其他

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

输入：nums = [3,4,2]输出：6解释：删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。

code

https://leetcode.cn/problems/delete-and-earn/solutions/758416/shan-chu-bing-huo-de-dian-shu-by-leetcod-x1pu/?envType=study-plan-v2&envId=dynamic-programming

【leetcode刷题记录】（java）动态规划

class Solution { public int deleteAndEarn(int[] nums) { int max=0; for (int num : nums) { max=Math.max(max,num); } int []sum=new int[max+1]; for (int num : nums) { sum[num]+=num; } return rob(sum); } private int rob(int sum[]){ int n=sum.length; int dp[]=new int[n]; dp[0]=sum[0]; dp[1]=Math.max(sum[0],sum[1]); for (int i=2;i<n;i++){ dp[i]=Math.max(dp[i-2]+sum[i],dp[i-1]); } return dp[n-1]; }}

712. 两个字符串的最小ASCII删除和

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = \"sea\", s2 = \"eat\"输出: 231解释: 在 \"sea\" 中删除 \"s\" 并将 \"s\" 的值(115)加入总和。在 \"eat\" 中删除 \"t\" 并将 116 加入总和。结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

code

初始化https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/solutions/1629453/by-lfool-lfpu/?envType=study-plan-v2&envId=dynamic-programming

dp[i][j] 表示子串 s1[0..i] 和 s2[0..j] 最小 ASCII 删除和

那么「状态转移方程」是什么呢？(有点逆过程的意思！！！)

如果 s1[i] = s2[j]，dp[i][j] = dp[i - 1][j - 1] (不需要被删除)
如果 s1[i] != s2[j]，dp[i][j] = Math.min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j])

【leetcode刷题记录】（java）动态规划

class Solution { public int minimumDeleteSum(String s1, String s2) { int n1 = s1.length(), n2 = s2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; // base case for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1); for (int i = 1; i <= n2; i++) dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1); for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { int c1 = s1.charAt(i - 1); int c2 = s2.charAt(j - 1); // 相等情况 if (c1 == c2)  dp[i][j] = dp[i - 1][j - 1]; // 不等情况 else  dp[i][j] = Math.min(dp[i][j - 1] + c2, dp[i - 1][j] + c1); } } return dp[n1][n2]; }}

673. 最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意这个数列必须是严格递增的。

示例 1:

输入: [1,3,5,4,7]输出: 2解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]输出: 5解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

code

【leetcode刷题记录】（java）动态规划

class Solution { public int findNumberOfLIS(int[] nums) { int n = nums.length, maxLen = 1; if(n == 1) return 1; int dp[] = new int[n];// dp[i]表示 i以及i之前 以nums[i]结尾的最长递增子序列的长度 int count[]=new int[n];//到nums[i]为止的最长递增子序列个数 Arrays.fill(dp, 1); Arrays.fill(count, 1); for(int j=1;j< nums.length;j++){ for(int i=0;i<j;i++){ if(nums[j]>nums[i]){  // [1,3,5,4,7] 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]  if(dp[i]+1>dp[j]){//i=2 dp[4]=0, dp[2]=3,,dp[2]+1=4>dp[4],dp[4]=4 dp[j]=dp[i]+1; //如果dp[i] + 1 > dp[j]，说明最长递增子序列的长度增加了，dp[i] = dp[j] + 1，长度增加，数量不变 count[j] = count[i] count[j]=count[i];  }else if(dp[i]+1==dp[j]){//i=3 dp[4]=4, dp[3]=3,,dp[3]+1=4 == dp[4], 长度为4的最长递增子序列个数+1 //如果dp[i] + 1 == dp[j]，说明最长递增子序列的长度并没有增加，但是出现了长度一样的情况，数量增加 count[j] += count[i] count[j]+=count[i];  } } } maxLen=Math.max(maxLen,dp[j]); } int res=0; for (int j=0;j<nums.length;j++){ if(dp[j]==maxLen){ res+=count[j]; } } return res; }}

1218. 最长定差子序列(已知公差)

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

输入：arr = [1,2,3,4], difference = 1输出：4解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1输出：1解释：最长的等差子序列是任意单个元素。

code 一维数组动态规划双层循环

class Solution { public int longestSubsequence(int[] arr, int difference) { int n = arr.length; int[] dp = new int[n]; Arrays.fill(dp,1); int maxlen=1; for (int j = 1; j < n; j++) { for (int i = 0; i < j; i++) { if (arr[i] + difference == arr[j]) {  dp[j]=Math.max(dp[j],dp[i]+1); } } maxlen=Math.max(maxlen,dp[j]); } return maxlen; }}

code hashmap 优化

class Solution { public int longestSubsequence(int[] arr, int difference) { int res=0; Map<Integer,Integer> dp=new HashMap<>(); for (int a : arr) { //获取到当前位置符合定差的最大长度 int max = dp.getOrDefault(a - difference, 0) + 1; //更新map dp.put(a, max); //对比选择最大长度 res = Math.max(res, max); } return res; }}

1027. 最长等差数列（怎么处理不知道的公差?）

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]输出：4解释： 整个数组是公差为 3 的等差数列。

code 怎么处理不知道的公差?

https://leetcode.cn/problems/longest-arithmetic-subsequence/solutions/2239444/python3javacgotypescript-yi-ti-yi-jie-do-h9lz/

dp[i][j]表示以nums[i]结尾，公差为j-500的最长等差子序列长度

class Solution { public int longestArithSeqLength(int[] nums) { int n = nums.length; int ans = 0; int[][] f = new int[n][1001];//dp[i][j]表示以nums[i]结尾，公差为j-500的最长等差子序列长度 for (int i = 1; i < n; ++i) { for (int k = 0; k < i; ++k) { int j = nums[i] - nums[k] + 500;//这里j当做数组下标使用，不能为负数，所以+500 f[i][j] = Math.max(f[i][j], f[k][j] + 1); ans = Math.max(ans, f[i][j]); } } return ans + 1; }}

【leetcode刷题记录】（java）动态规划

文章目录

一、动态规划

509. 斐波那契数

状态压缩之后的：

没有压缩

70. 爬楼梯

代码

746. 使用最小花费爬楼梯

62. 不同路径

代码

63. 不同路径 II

代码

343. 整数拆分

代码

96. 不同的二叉搜索树

Code

二、背包问题（动态规划）

01背包

二维数组

1、dp数组定义 状态转移方程

2、初始化

3、代码

一维数组 （滚动数组）

1、dp数组定义 状态转移方程

2、初始化

3、代码

416. 分割等和子集

代码

1049. 最后一块石头的重量 II

code

494. 目标和

思路

dp数组含义、递推公式、初始化

二维数组

一维数组 滚动数组

Code

474. 一和零

思路

code

三、 完全背包

二维数组形式：

一维数组：

区分01背包和完全背包（二维数组）

手推： 区分01背包和完全背包（一维数组）

01背包

完全背包

518. 零钱兑换 II

二维数组

Code

一维数组

四、拓展：完全背包问题，双层循环的顺序，求组合还是求排列数？

先遍历物品，内层正序，求组合数

先遍历容量，内层正序，求排列数

原理解释

当不涉及组合排列的时候 建议先遍历物品

377. 组合总和 Ⅳ

322. 零钱兑换

code

疑问：直观理解 dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

代码或者：

279. 完全平方数

code 完全背包

139. 单词拆分

code

198. 打家劫舍

code

213. 打家劫舍 II

code

(巧妙)337. 打家劫舍 III

code

121. 买卖股票的最佳时机（一股 股票，1次买卖）

贪心 code

动态规划 code

122. 买卖股票的最佳时机 II （一股 股票，多次买卖）

code

123. 买卖股票的最佳时机 III （一股 股票，2次买卖）

code

188. 买卖股票的最佳时机 IV （一股 股票，k次买卖）

code

1、dp数组定义状态转移方程

一维数组（滚动数组）

1、dp数组定义状态转移方程

一维数组滚动数组

三、完全背包

手推：区分01背包和完全背包（一维数组）

当不涉及组合排列的时候建议先遍历物品

121. 买卖股票的最佳时机（一股股票，1次买卖）

122. 买卖股票的最佳时机 II （一股股票，多次买卖）

123. 买卖股票的最佳时机 III （一股股票，2次买卖）

188. 买卖股票的最佳时机 IV （一股股票，k次买卖）

code 一维数组动态规划双层循环