动态规划特点
1、重叠子问题
2、状态转移方程（最关键）
3、最优子结构
解题套路
1、明确【状态】 2、明确【选择】 3、明确dp函数/数组的定义 4、明确base case（最简单的情况）
穷举+状态转移（其实动态规划问题也是穷举了所有的可能性，只是这里的穷举有点特殊，这里的穷举依赖于之前的状态，以减少时间复杂度，避免不必要的重复计算，从而引出状态转移方程的概念。求解状态n时，与求解状态n-1的时候的区别。它不一定是与最近的状态产生关联，而是有可能与之前所有的状态比较得到一个最的优解）。
框架
//初始化base casedp[0][0][...]=base//进行状态转移for 状态1 in 状态1的所有值for 状态2 in 状态2的所有值for ....dp[状态1][状态2][....]==求最值（选择1，选择2）
动态规划一般有两种解题的思路：
- 自顶向下的，使用备忘录的递归方法
- 自底向上的，使用dp数组的循环方法
在普通的动态规划问题中，可以优先考虑使用自底向上的dp数组方法。
关键点：在于寻找正确的状态转移方程
斐波那契数列
70. 爬楼梯
| 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 |
|---|
题解思路：确定状态数组dp[i] 为到达第 i 阶台阶的方法。
问题划分：第n阶台阶可以由n-1的台阶走一步或者是n-2的台阶走两步来实现。
状态转移方程：F(n)=F(n-1)+F(n-2)
class Solution {public int climbStairs(int n) {if(n<=2)return n;int pre1=1;//第一个台阶只有一个选择int pre2=2;//第二个台阶可有两个选择for(int i=3;i<=n;i++){int curr=pre1+pre2;pre1=pre2;pre2=curr;}return pre2;}}
198. 打家劫舍
| 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 |
|---|
题解思路：
- 定义子问题
- 写出子问题的递推关系
- 确定DP数组的计算顺序
- 空间优化（可选）
步骤一：定义子问题
原问题：偷n间房子的最大金额
子问题：偷k间房子的最大金额
步骤二: 子问题的递推关系（依赖关系）
两者之间取最优
步骤三：确定计算顺序
dp数组的顺序是从左到右，f（k）依赖于f（k-1）和f（k-2）
class Solution {
public int rob(int[] nums) {
if (nums.length == 0)
return 0;
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
int res = Math.max((nums[i - 1] + dp[i - 2]), dp[i - 1]);
dp[i] = res;
}
return dp[nums.length];
}
}
上个屋子的最优解或者是当前屋子+上上个屋子的最优解
步骤四：优化空间
dp数组无需存储所有的结果，每次只需要与当前结果相关的上两个结果集即可
public int rob(int[] nums) {
int prev = 0;
int curr = 0;
// 每次循环，计算“偷到当前房子为止的最大金额”
for (int i : nums) {
// 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
// dp[k] = max{ dp[k-1], dp[k-2] + i }
int temp = Math.max(curr, prev + i);
prev = curr;
curr = temp;
// 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
}
return curr;
}
213. 打家劫舍 II
环形打劫算法：可以切分为两种情况求解
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
private int rob(int[] nums, int first, int last) {
int pre2 = 0, pre1 = 0;
for (int i = first; i <= last; i++) {
int cur = Math.max(pre1, pre2 + nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
矩阵路径
64. 最小路径和
给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。 输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。 |
|---|
- 状态定义
设dp为大小m*n矩阵，其中dp[ i ][ j ]的值代表走到（i，j）的最小路径和
- 转移方程
走到当前单元格的最小路径为，从左方单元格（i-1，j）与从上方单元格（i，j-1）走来的两个最小路径中的较小者+当前单元格值grid[ i ][ j ]
1、当左边和上边都不是矩阵边界时： 即当i ！= 0，j！=0 。dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]dp[i] 2、当只有左边是矩阵边界时： 只能从上面来，即当i = 0, j ！=0时， dp[i][j] = dp[i][j - 1] + grid[i][j]； 3、当只有上边是矩阵边界时： 只能从左面来，即当i ！= 0, j = 0时， dp[i][j] = dp[i - 1][j] + grid[i][j]； 4、当左边和上边都是矩阵边界时： 即当i = 0, j = 0i=0,j=0时，其实就是起点， dp[i][j] = grid[i][j]dp[i][j]=grid[i][j]；
- 初始状态
- dp 初始化即可，不需要修改初始 00 值。
- 返回值：
- 返回 dpdp 矩阵右下角值，即走到终点的最小路径和。
还是一个关于选择的问题，每到一个点选择到达该点的一个最优值
- 返回 dpdp 矩阵右下角值，即走到终点的最小路径和。
class Solution {
public int minPathSum(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (i == 0 && j == 0) continue;
else if (j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];
else if (i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];
else grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
}
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 示例 1： 输入：m = 3, n = 7 输出：28 |
|---|
题解思路：
求解到达目标点的最大路径数，是否可以等价于每一个点都选取到达该点的最大路径数
暴力解法：遍历所有的情况
动态规划：每个节点的情况在暴力解法中其实存在重复求解的可能性，可以优化
到达（m,n）点的路径等于（m-1，n）+（m，n-1）的路径之和，有点类似于跳楼梯的问题
class Solution {
public int uniquePaths(int m, int n) {
int[][] res=new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0)
res[0][j]=1;
else if(j==0)
res[i][0]=1;
else
res[i][j]=res[i-1][j]+res[i][j-1];
}
}
return res[m-1][n-1];
}
}
类似于跳楼梯的问题，但是要处理一下边界问题
优化解法（空间优化）
当前坐标的值只与左边和上面的值是有关的，和其他的无关，所以可以将二维数组改为一维数组
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
//初始化第一行和第一列
Arrays.fill(cur,1);
for (int i = 1; i < m;i++){
for (int j = 1; j < n; j++){
//当前行的dp等于上一行的dp+当前行的dp
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
}
数组区间和
303. 区域和检索 - 数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。 |
|---|
class NumArray {
private int[] dp;
public NumArray(int[] nums) {
dp = new int[nums.length + 1];
for (int i = 1; i <= nums.length; i++) {
dp[i]=dp[i-1]+nums[i-1];
}
}
public int sumRange(int i, int j) {
return dp[j+1]-dp[i];
}
}
关键点：代码中使用状态转换dp[j+1]-dp[i]+dp数组dp[i]=dp[i-1]+nums[i-1]; 注意点：dp的边界问题
413. 等差数列划分
| 如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。 例如，以下数列为等差数列: [1, 3, 5, 7, 9] [7, 7, 7, 7] [3, -1, -5, -9] 示例: A = [1, 2, 3, 4] 返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。 |
|---|
class Solution {
public int numberOfArithmeticSlices(int[] A) {
int[] dp = new int[A.length];//注意这里的动态数组表达的意思是包含该元素时有多少个等差数列
int sum = 0;
for (int i = 2; i < dp.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
sum += dp[i];
}
}
return sum;
}
}
分割整数
343. 整数拆分
| 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 |
|---|
题解思路：
1、整数n的拆分对应的子问题整数n-1的拆分（确定使用动态规划思路）
2、接下来的问题状态dp应该是什么？dp【i】应该代表正整数 i 可以得到的最大的乘积
3、dp【i】对于之前的依赖关系是怎么样的？是依赖于其中一个？前两个？异或是前面所有的元素都有可能呢？
推出动态规划的转移方程：dp[i] = Math.max(dp[i], Math.max(dp[i - j] j, (i - j) j));
注：这里可能会忽视掉的一个元素(i - j) * j)，只考虑到与之前dp的关系，但是自己单独存在也是一种可能性
class Solution {
public int integerBreak(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++) {
dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
}
}
return dp[n];
}
}
279. 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如， 1、4、9 和 16 都是完全平方数，而 3 和 11 不是。示例 1： 输入：n = 12输出：3 解释： 12 = 4 + 4 + 4 |
|---|
题解思路：
1、正整数n的组成元素最少——>正整数（n-1）的组成元素最少：确定使用动态规划的思路
2、dp【i】与之前的哪些元素有关系。因为是由平方数组成，所以上一个元素与当前元素的差值一定是一个平方数。
推出动态规划的公式：dp[i]=Math.min(dp[i],dp[i-j*j]+1);
class Solution {
public int numSquares(int n) {
int[] dp=new int[n+1];
for(int i=1;i<=n;i++){
dp[i]=i;
for(int j=1;j*j<=i;j++){
dp[i]=Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
注：j 的终止条件：j*j<=i；超过这个值就没有意义了。动态规划方程自己一开始也想错了
dp[i]=Math.min(dp[i],dp[j]+1)；
91. 解码方法
| 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
- "AAJF" ，将消息分组为 (1 1 10 6)
- "KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = “12”
输出：2
解释：它可以解码为 “AB”（1 2）或者 “L”（12）。 |
| —- |
题解思路：1、依旧是一个子问题的替换确定使用动态规划的思路
2、确定dp【i】和之前的哪些dp有关系呢？
2.1 当我们新增一位数字的时候，要么不改变前面的任何情况，新增的这一位数字自己单独解码。
2.2 要么新增的这一位可以与前面的一位一起构成一个解码元素，而前面的前面的元素不被影响到。
class Solution {
public int numDecodings(String s) {
int length=s.length();
s=" "+s;
int[] dp=new int[length+1];
char[] ch=s.toCharArray();
dp[0]=1;
//动态转移方程，当前位置的拆分
for(int i=1;i<=length;i++){
int a=ch[i]-'0',b=(ch[i-1]-'0')*10+(ch[i]-'0');
if(a>=1&&a<=9) dp[i]=dp[i-1];
if(b>=10&&b<=26&&i>1) dp[i]+=dp[i-2];
}
return dp[length];
}
}
注：1、通过s=“ ”+s的方式增加索引位是真的牛逼
2、最后分析的结果有点像是爬楼梯问题。
最长递增子序列
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 。 |
|---|
题解思路：要求最长子序列（可以删除中间值），只要后面的值大于前面的值就可以构成最长子序列
1、判断子问题dp表示在当前位可获得的最长子序列的长度
2、判断当前位与之前位的关系，可以发现，当前位可能和之前的任意一位构成子序列，所以需要全遍历
int length = nums.length;
int[] dp = new int[length];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 0; i < length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
max = Math.max(max, dp[i]);
}
}
}
return max;
646. 最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。 示例： 输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4] |
|---|
题解思路：数对：第一个数字大于第二个数字，感觉有点像是重叠区间的问题
dp表示当前数对可以形成的最长数对链，因为不需要顾及顺序问题，所以可以需要遍历所有的情况
class Solution {
public int findLongestChain(int[][] pairs) {
if(pairs==null||pairs.length==0)
return 0;
//排序，保证dp是从很小到大遍历的
Arrays.sort(pairs,(int[] o1,int[]o2)->o1[0]-o2[0]);
//总共含有的数对数量
int n=pairs.length;
//创建dp数组
int[] dp=new int[n];
//每一个数对，可以自己单独构成一个数对链
Arrays.fill(dp,1);
int res=1; //当只存在一个元素时的结果
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(pairs[i][0]>pairs[j][1]){
dp[i]=Math.max(dp[i],dp[j]+1);
res=Math.max(res,dp[i]);
}
}
}
return res;
}
}
376. 摆动序列
| 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。 示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。 |
|---|
题解思路：动态规划
dp代表当前索引下最长摆动序列的长度，因为序列是可以删除元素获得，所以当前dp是和之前的所有的元素都有可能有关系。那这个关系是什么呢？还是只要考虑前两个元素？
以当前的元素来看，可以是处于一个上升的状态，也可以是处于一个下降的状态，这两状态就需要两个dp来保证。
每当我们选择一个元素作为摆动序列的一部分时，这个元素要么是上升的，要么是下降的，这取决于前一个元素的大小。
- up【i】表示以前 i 个元素中的某一个为结尾的最长的上升摆动序列的长度
- down【i】表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。
参考图片自己的代码：
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
int[] maxdp = new int[n];
int[] mindp = new int[n];
Arrays.fill(maxdp, 1);
Arrays.fill(mindp, 1);
int max = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
maxdp[i] = mindp[i - 1] + 1;
mindp[i] = mindp[i - 1];
} else if (nums[i] < nums[i - 1]) {
maxdp[i] = maxdp[i - 1];
mindp[i] = maxdp[i - 1] + 1;
}
max = Math.max(max, Math.max(maxdp[i], mindp[i]));
}
return max;
}
}
但是过不了所有的测试用例，问题：少了相等的时候的判断
官方正确版：
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int[] up = new int[n];
int[] down = new int[n];
up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = Math.max(up[i - 1], down[i - 1] + 1);
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
up[i] = up[i - 1];
down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
} else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return Math.max(up[n - 1], down[n - 1]);
}
}
由此可以看出：其实动态规划就是一个填表的过程。
空间优化：
观察图片可得：当前位的两个状态其实也只是与之前的这两个状态相关，所以我们可以考虑将空间优化，只用两个状态量来保存即可
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length==0) return 0;
int n = nums.length;
int up = 1;
int down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
最长公共子序列
1143. 最长公共子序列
| 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回 0 。
一个字符串的 子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。 |
| —- |
题解思路：最长公共子序列问题是典型的二维动态规划问题
求解两个数组或者是字符串的最长公共子序列问题，肯定使用动态规划
确定状态：dp【i】【j】表示text1【0：i】和text2【0：j】的最长公共子序列的长度
确定边界情况：当 i=0 或 j=0时，dp[i][j]=0。
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
char c1 = text1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = text2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
背包问题
这里的元素之间的顺序性可以根据题518和题377对比理解。在不考虑顺序性的情况下（1，2）和（2，1）视为同一个元素，而考虑元素性则视为不同的元素。将nums数组写在外循环其实也意味着要么取到（1，2），要么取到（2，1）。不会同时取到。
分析：
1、组合问题：dp[i]+=dp[i-num]；377、494、518
2、True、false问题： dp[i]=dp[i] or dp[i-num]；139、416
3、最大最小问题：dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)；474、322
| 0-1背包依赖的是正上方和正上方左边的格子 完全背包依赖的是正上方和当前行左边的格子 |
|---|
0-1背包问题
416、474、494、879
| 给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？ 输入如下： N = 3, W = 4 wt = [2, 1, 3] val = [4, 2, 3] |
|---|
题目中的物品不可以分割，要么装进包里，要么不装。
转义：当从n个物品种选择多个物品放包里而物品体积综合不超过包的容量m时，能够得到的最大价值是多少？
状态分析：物品的个数和背包的容量两个状态。
明确【状态】和【选择】
状态：背包的容量和可选择的物品
选择：装入或者不装
- 子问题：二维dp数组dp[i][j]：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。
比如说，如果 d p [ 3 ] [ 5 ] = 6 dp[3][5] = 6dp[3][5]=6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。 根据这个定义，我们想求的最终答案就是 dp[N][W]。
base case： 当没有物品 或 背包没有容量时，dp [ 0 ] [ . . . ] = dp [ . . . ] [ 0 ] = 0 dp[0][…] = dp[…][0] = 0dp[0][…]=dp[…][0]=0
状态转移：
物品 i 有两种选择—装进背包和不装，设第 i 件物品体积为 w，价值为 v。
1、物品 i 不装进背包，最大价值 d p [ i ] [ j ] = d p [ i − 1 ] [ j ]
2、物品 i 装进背包，最大价值 d p [ i ] [ j ] = d p [ i − 1 ] [ j − w ] + v
因此，0-1 背包的状态转移方程为：
d p [ i ] [ j ] = M a t h . m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w ] + v )
在装第**i**个物品的前提下，背包能装的最大价值是多少？
显然，你应该寻求剩余重量w-wt[i-1]限制下能装的最大价值，加上第i个物品的价值val[i-1]，这就是装第i个物品的前提下，背包可以装的最大价值。
class Solution {
public int maximalSquare(char[][] matrix) {
//i表示到达第i个物品，j表示背包的容量
int[][] dp=new int[N+1][W+1];
for(int i=1;i<N+1;i++){
int w=weight[i-1],v=values[i-1];
for(int j=1;j<W+1;j++){
if(j>=w)
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w]+1);
else
dp[i][j]=dp[i-1][j];
}
}
return dp[N][W];
}
}
一维DP
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 |
|---|
题解思路：这道题可以转换为0-1背包问题。题目要求的内容可以理解为给定一个非空数组，能否从中选取若干个数值(状态1)，使得总重量为sum/2（状态2）。
面对动态规划问题首先要明确的是状态，然后是状态的转移。在这个问题中，变化的状态是选取的值（选或者不选）。还有一个状态是背包的重量（个人感觉这个点其实有点难转过弯来）。
所以最终状态定义为：dp[ i ][ j ]表示从数组的【0，i】区间内挑选一些正整数，使得这些数字的和正好为 j 。
public class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1)
return false;
int target = sum / 2;
boolean[][] dp = new boolean[len + 1][target + 1];
//Base case
for (int i = 0; i < len + 1; i++)
dp[i][0] = true;
for (int i = 1; i < len + 1; i++) {
for (int j = 1; j < target + 1; j++) {
if (j < nums[i - 1])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i - 1]];
}
}
return dp[len][target];
}
}
空间优化
实际上在填表的过程中可以知道，填写当前格时，只参考了它上面的那个位置一级左上角某个位置的值。
public class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1)
return false;
int target = sum / 2;
boolean[] dp=new boolean[target+1];
//Base case
dp[0]=true;
for(int i=0;i<len;i++){
for(int j=target;j>=0;j--){
if (j>=nums[i])
dp[j]=dp[j]||dp[j-nums[i]];
}
}
return dp[target];
}
}
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 。 |
|---|
考虑这个问题，大概的思路（default）
for(int j=0;j<s.length();j++){
for(int i=0;i<j;i++){
//判断这个值可不可以加入进来
dp[i][j]==Math.max(dp[i][j],dp[i][j-1]+1);
//怎么存储0和1 的值呢？
思路：把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。
| 动态规划的思路是：物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选。 定义状态：尝试题目问啥，就把啥定义成状态。dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串最大数量。 状态转移方程： dp[i][j][k]=dp[i - 1][ j ][ k ] （不选择当前考虑的字符串） dp[i - 1][ j - 当前字符串使用 0 的个数][k - 当前字符串使用 1 的个数] + 1 （选择当前考虑的字符串 ） 初始化：为了避免分类讨论，通常多设置一行。这里可以认为，第 00 个字符串是空串。第 00 行默认初始化为 00。 输出：输出是最后一个状态，即：dp[len][m][n]。 |
|---|
494. 目标和
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例： 输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5 解释： -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 一共有5种方法让最终目标和为3。 |
|---|
题解思路：枚举递归
class Solution {
private static int count;
public int findTargetSumWays(int[] nums, int target) {
count = 0;
dfs(nums, target, 0);
return count;
}
public void dfs(int[] nums, int target, int index) {
if (index == nums.length) {
if (target == 0)
count++;
} else {
dfs(nums, target + nums[index], index + 1);
dfs(nums, target - nums[index], index + 1);
}
}
}
题解思路2：动态规划
1、确定状态值：用 dp[ i ][ j ]表示用数组中的前 i 个元素，组成和为 j 的方案数。
2、思考第 i 个数 nums[ i ]和之前的数的关系。考虑第 i 个数 nums[i]，它可以被添加 + 或 -，因此状态转移方程如下：
dp[ i ][ j ] = dp[i - 1][ j - nums[ i ]] + dp[ i - 1 ][ j + nums[ i ] ]
class Solution {
public int findTargetSumWays(int[] nums, int target) {
//题解思路：分析状态，每一个位置的状态选择都有两种情况：选择+1或者选择-1;
//确定dp状态变量dp[i][j]，i表示选择到第i个数字,j表示此时的容量。
//那么dp[i][j]表示的意思就是当选择到第i个数字时，构成j容量的个数。
//容量可能出现负数的情况，然而数组是不能使用负数作为下标索引的，所以需要特殊处理一下。
//考虑状态转移方程：i数字的情况其实只能从i-1的情况转移而来。
//dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j+1]+1;
if(nums.length==Math.abs(target))
return 1;
int m=nums.length;//行
int n=2*m+1;//列
int[][] dp=new int[m][n];
//初始化dp Base
for(int j=0;j<n;j++){
if((j==m-1)||(j==m+1)){
dp[0][j]=1;
}
}
for(int i=1;i<m;i++){
for(int j=1;j<n-1;j++){
dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
}
}
return dp[m-1][m+target];
}
}
如果数字只有1的情况下，上述的代码成立，但是如果还有其他的值，不成立，重新修改。观察上面的代码由特殊性变为通用性，我们需要改进的地方在哪里？
1、列坐标的长度不是数组的长度来计算，而是通过数组的和来计算
2、动态转移方程：变化的大小 不应该是1，而是nums【i】
3、边界的控制，不妨让他计算所有的结果，再从中挑出我们自己需要的就是
TODO
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int num:nums)
sum+=num;
//特殊情况，判断直接跳出
if(Math.abs(target)>Math.abs(sum)) return 0;
//dp数组的行数
int m=nums.length;
//dp数组的列数
int n=2*sum+1;
int[][] dp=new int[m][n];
//初始化dp Base（注意这里存在的一种特殊情况）
if(nums[0]==0)
dp[0][sum]=2;//特殊情况
else{
dp[0][sum-nums[0]]=1;
dp[0][sum+nums[0]]=1;
}
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
if(j-nums[i]>=0)
dp[i][j]+=dp[i-1][j-nums[i]];
if(j+nums[i]<n)
dp[i][j]+=dp[i-1][j+nums[i]];
}
}
return dp[m-1][sum+target];
}
}
注：特殊情况：nums中第一个元素为0的情况： dp[0][sum]=2;（加0或者减0都是0）故为2。
完全背包
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。可以认为每种硬币的数量是无限的。示例 1： 输入：coins = [1, 2, 5], amount = 11输出： 3解释：11 = 5 + 5 + 1 |
|---|
题解思路1：自底向上的dp数组方法
创建dp数组，每个总金额的最小硬币数都存在两种选择情况，一种就是本身另外一种就是上一个最优+1
class Solution {
public int coinChange(int[] coins, int amount) {
if (coins.length == 0)
return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);//amount+1正常时不可能出现的值
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0)
//选取当前结果或者是上个最优解的结果+一个硬币
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
return dp[amount]==(amount+1)?-1:dp[amount];
}
}
题解思路2：自顶向下的备忘录方法
题解思路： 向下迭代，寻求每一个金额的最少的硬币个数
class Solution {
int[] meno;
public int coinChange(int[] coins, int amount) {
if (coins.length == 0)
return -1;
meno = new int[amount];
return findWay(coins, amount);
}
//meno[n]表示钱币n+1可以被换取的最少的硬币数，不能换取就为-1；
//findWay函数的目的是为了找到amount数量的零钱可以兑换的最少硬币数量，返回其值int
public int findWay(int[] coins, int amount) {
if (amount < 0)
return -1;
if (amount == 0) {
return 0;
}
//记忆化的处理，如果meno[n]存在就直接使用，不存在就计算出
if (meno[amount - 1] != 0)
return meno[amount - 1];
int min = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
int res = findWay(coins, amount - coins[i]);
if (res >= 0 && res < min) {
min = res + 1;//加一是为了得到res结果的那个步骤中，兑换的一个硬币
}
//以下写法可以更好理解动态规划的一个选择问题
if (res >= 0) {
min = Math.min(res + 1, min);
}
}
meno[amount - 1] = (min == Integer.MAX_VALUE ? -1 : min);
return meno[amount - 1];
}
}
}
518. 零钱兑换 II
| 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 |
|---|
题解思路：初始我考虑的情况是类似于爬楼梯问题，但是这样的子问题定义是有问题的，内部会有重复的情况。
首先，我们要确立的一个基本的条件是：凡是背包问题都从选和不选两种情况来考虑。先把问题定义的简单一点。二维数组：i 代表当前的物品，j 代表背包的容量。
dp[ i ][ j ]的含义：若只使用前 i 个物品，当背包容量为 j 时，有 dp[ i ][ j ] 种方法可以装满背包。
思考在选与不选的情况下：dp【i】【j】应该和前面的什么状态是有关系的？
1、我们不选当前的硬币的话：dp【i】【j】=dp【i-1】【j】；
2、我们选择当前硬币的话：dp【i】【j】=dp【i】【j-nums【i】】；
class Solution {
public int change(int amount, int[] coins) {
int n=coins.length;
int[][] dp=new int[n+1][amount+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++)
if(j-coins[i-1]>=0)
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];//要么一个不选要么一个或多个
else
dp[i][j]=dp[i-1][j];
}
return dp[n][amount];
}
}
状态压缩
int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1; // base case
for (int i = 0; i < n; i++)
for (int j = 1; j <= amount; j++)
if (j - coins[i] >= 0)
dp[j] = dp[j] + dp[j-coins[i]];
return dp[amount];
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[] dp=new int[target+1];
dp[0]=1;
for(int j=0;j<=target;j++){
for(int i=0;i<nums.length;i++){
if(j>=nums[i])
dp[j]+=dp[j-nums[i]];
}
}
return dp[target];
}
}
139. 单词拆分
| 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。 |
| —- |
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) { // 对物品的迭代应该放在最里层
int len = word.length();
if (len <= i && word.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
字符串问题
583. 两个字符串的删除操作
| 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。 示例： 输入: “sea”, “eat” 输出: 2 解释: 第一步将”sea”变为”ea”，第二步将”eat”变为”ea” |
|---|
题解思路：题目的意思就是求两个字符串的最大公共子字符串
题解方法1：递归+记忆化
class Solution {
public int minDistance(String s1, String s2) {
int[][] meno=new int[s1.length()+1][s2.length()+1];
return s1.length() + s2.length() - 2 * lcs(s1, s2, s1.length(), s2.length(),meno);
}
public int lcs(String s1,String s2,int m,int n,int[][] meno){
if (m==0||n==0)
return 0;
if (meno[m][n]>0)
return meno[m][n];
if (s1.charAt(m-1)==s2.charAt(n-1))
meno[m][n]=1+lcs(s1,s2,m-1,n-1,meno);
else
meno[m][n]=Math.max(lcs(s1, s2, m, n-1,meno),lcs(s1,s2,m-1,n,meno));
return meno[m][n];
}
}
题解方法2：
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。示例 1： 输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。 |
|---|
方法1：暴力匹配法
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组
char[] charArray = s.toCharArray();
// 枚举所有长度大于 1 的子串 charArray[i..j]
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
/**
* 验证子串 s[left..right] 是否为回文串
*/
private boolean validPalindromic(char[] charArray, int left, int right) {
while (left < right) {
if (charArray[left] != charArray[right]) {
return false;
}
left++;
right--;
}
return true;
}
}
方法2：动态规划
题解思路：对于回文串来说，它的子串也必须满足回文串的特性，例如”ababa”。所以对于一个子串来说的要满足回文串的特性：P（i，j）=P（i+1，j-1）^（Si==Sj）。
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) return s;
int maxLen = 1; //确保有一个元素的输出
int begin = 0;
boolean[][] dp = new boolean[len][len];
char[] chars = s.toCharArray();
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
if (j - i == 1 && chars[i] == chars[j])
dp[i][j] = true;
else
dp[i][j] = false;
if (j - i > 1)
dp[i][j] = dp[i + 1][j - 1] && chars[i] == chars[j];
if (dp[i][j] && j - i + 1 > maxLen) {
begin = i;
maxLen = j - i + 1;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
在这里需要注意的是for循环的写法，因为动态规划要满足【无后效性】，当前值仅仅依赖于前面已经计算出来的值。
如图1所示遍历方式，遍历到（0，3）是依赖的状态是（1，2）但是，（1，2）在（0，3）的后面计算。
72. 编辑距离
| 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’) |
| —- |
题解思路：word1和word2的编辑距离为x，就意味着经过x步后，word1变为了word2.
定义dp[ i ][ j ]的含义为：word1的前 i 个字符和 word2 的前 j 个字符的编辑距离。意思就是word1的前 i 个字符，变成word2的前 j 个字符，最少需要这么多步。
例如 word1 = “horse”，word2 = “ros”，那么dp[3][2]=X就表示”hor”和“ro”的编辑距离，即把”hor”变成“ro”最少需要X步。
如果下标为零则表示空串，比如：dp[0][2]就表示空串””和“ro”的编辑距离
定理一：如果其中一个字符串是空串，那么编辑距离是另一个字符串的长度。比如空串“”和“ro”的编辑距离是2（做两次“插入”操作）。再比如”hor”和空串“”的编辑距离是3（做三次“删除”操作）。
定理二：当 i>0，j>0时（即两个串都不空时）dp[ i ][ j ]=min(dp[ i-1 ][ j ]+1,dp[ i ][ j-1 ]+1,dp[ i-1 ][ j-1 ]+int(word1[ i ] !=word2[ j ]))。
啥意思呢？举个例子，word1 = “abcde”, word2 = “fgh”,我们现在算这俩字符串的编辑距离，就是找从word1，最少多少步，能变成word2？那就有三种方式：
- 知道”abcd”变成”fgh”多少步（假设X步），那么从”abcde”到”fgh”就是”abcde”->”abcd”->”fgh”。（一次删除，加X步，总共X+1步）
- 知道”abcde”变成“fg”多少步（假设Y步），那么从”abcde”到”fgh”就是”abcde”->”fg”->”fgh”。（先Y步，再一次添加，加X步，总共Y+1步）
- 知道”abcd”变成“fg”多少步（假设Z步），那么从”abcde”到”fgh”就是”abcde”->”fge”->”fgh”。（先不管最后一个字符，把前面的先变好，用了Z步，然后把最后一个字符给替换了。这里如果最后一个字符碰巧就一样，那就不用替换，省了一步）
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
//创建dp数组
int[][] dp = new int[len1 + 1][len2 + 1];
//Base case
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if (word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
else{
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
}
}
}
return dp[len1][len2];
}
}
96. 不同的二叉搜索树
| 给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: 5 |
|---|
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i]+= dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
动态规划问题考虑的思路：n个节点组成的二叉搜索树能不能替换为n-1个节点呢？
但是这里的思路在于：
假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
G(n) = f(1) + f(2) + f(3) + f(4) + … + f(n)G(n)=f(1)+f(2)+f(3)+f(4)+…+f(n)
当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
f(i)=G(i−1)∗G(n−i)
通过这样的方式转换了状态。
其实我们可以这样思考对于【1，2，3，4】和【4，5，6，7】构成的不同的二叉搜索树的个数其实是一样的。
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 示例 1: 输入: [2,3,-2,4] 输出: 6解释: 子数组 [2,3] 有最大乘积 6。 |
|---|
题解思路动态规划：一开始的思路是通过一个dp记录操作。但是会发现对于间隔负号的存在是无法AC的。所以考虑采用两个状态（最大与最小）。最小的状态主要是为了负数的时候考虑。
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 1) return nums[0];
int length = nums.length;
int[] maxDp = new int[length + 1];
int[] minDp = new int[length + 1];
maxDp[0] = 1;
minDp[0] = 1;
int max = Integer.MIN_VALUE;
for (int i = 1; i <= nums.length; i++) {
if (nums[i - 1] > 0) {
maxDp[i] = Math.max(nums[i - 1], nums[i - 1] * maxDp[i - 1]);
minDp[i] = Math.min(nums[i - 1], nums[i - 1] * minDp[i - 1]);
} else if (nums[i - 1] < 0) {
maxDp[i] = Math.max(nums[i - 1], nums[i - 1] * minDp[i - 1]);
minDp[i] = Math.min(nums[i - 1], nums[i - 1] * maxDp[i - 1]);
} else {
maxDp[i] = 0;
minDp[i] = 0;
}
max = Math.max(maxDp[i], Math.max(max, minDp[i]));
}
return max;
}
}
优化写法
class Solution {
public int maxProduct(int[] nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
int length = nums.length;
for (int i = 1; i < length; ++i) {
int mx = maxF, mn = minF;
maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
ans = Math.max(maxF, ans);
}
return ans;
}
}
354. 俄罗斯套娃信封问题
难度困难512
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
股票交易问题
309. 最佳买卖股票时机含冷冻期
| 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] |
| —- |
题解思路：用dp【i】表示第 i 天结束之后的【累计最大收益】，通过题意最多有以下三种状态
1、目前持有一只股票的累计最大收益记为 dp[ i ][ 0 ]；
2、目前不持有任何股票并处于冷冻期dp[ i ][ 1 ]；
3、目前不持有任何股票且不处于冷冻期dp[ i ][ 2 ]；
分析状态转移的过程：
在第 i 天的时候，我们可以在不违反规则的前提下进行【买入】或者【卖出】操作，此时第 i 天的状态就会从第 i-1 天的状态转移而来。我们也可以不进行任何的操作，此时第 i 天的状态就等同于第 i-1 天的状态。
对于dp[ i ][ 0 ]。持有的这个股票可以是dp[ i-1 ][ 0 ]持有的，也可以是在当天买入的，也就是dp[ i-1 ][ 2 ]-prices i ]。 | dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i])； | | —- |
对于dp[ i ][ 1 ]，不持有股票且处于冷冻期，说明当天执行了卖出操作。dp[ i ][ 1 ]=dp[ i-1 ][ 0 ]+prices[ i ]
对于dp[ i ][ 2 ]，不持有股票且不处于冷冻期，说明当天没有任何操作。 dp[ i ][ 2 ]=Math.max(dp[ i-1 ][ 1 ] ,dp[ i-1 ][ 2 ] );
class Solution { public int maxProfit(int[] prices) { //1、目前持有一只股票的累计最大收益记为 dp[ i ][ 0 ]； //2、目前不持有任何股票并处于冷冻期dp[ i ][ 1 ]； //3、目前不持有任何股票且不处于冷冻期dp[ i ][ 2 ]； int len=prices.length; int[][] dp=new int[len][3]; //Base case dp[0][0]=-prices[0]; dp[0][1]=0; dp[0][2]=0; for(int i=1;i<len;i++){ dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]); dp[i][1]=dp[i-1][0]+prices[i]; dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]); } return Math.max(dp[len-1][1],dp[len-1][2]); } }
714. 买卖股票的最佳时机含手续费
给定一个整数数组 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. |
|---|
dp[ i ]表示第 i 天结束后可以获得的最大的利益
持有/不持有？
二维DP数组
class Solution {
public int maxProfit(int[] prices, int fee) {
int len=prices.length;//天数
int[][] dp=new int[len][2];//持有和不持有两种状态
//Base case(0状态代表持有，1状态代表不持有)
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<len;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
}
return dp[len-1][1];
}
}
空间优化：一维DP数组
class Solution {
public int maxProfit(int[] prices, int fee) {
int len=prices.length;//天数
//int[][] dp=new int[len][2];//持有和不持有两种状态
//Base case(0状态代表持有，1状态代表不持有)
int i0=-prices[0];
int i1=0;
//dp[0][0]=-prices[0];
//dp[0][1]=0;
for(int i=1;i<len;i++){
i0=Math.max(i0,i1-prices[i]);
i1=Math.max(i1,i0+prices[i]-fee);
}
return i1;
}
}
123. 买卖股票的最佳时机 III
给定一个数组，它的第 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 。 |
|---|
题解思路：
由于我们最多可以完成两笔交易，因此在任意一天结束之后，会处于以下五种状态的一种：
1、未进行任何操作
2、只进行过一次买操作
3、进行了一次买操作和一次卖操作，即完成了一笔交易；
4、在完成了一笔交易的前提下，进行了第二次买操作；
5、完成了全部两笔交易。
由于第一个状态的利润显然为0，可以不记录，对于剩下的四个状态，分别将它们的最多利润记为buy1、sell1、buy2和sell2。
如果我们知道了第 i-1 天结束后的这四个状态，那么如何通过状态转移方程得到第 i 天结束后的这四个状态呢？
1、buy1=max{buy1,−prices[i]}
2、sell1=max{sell1,buy1+prices[i]}
3、buy2=max{buy2,sell 1 −prices[i]}
4、sell2=max{sell2,buy2+prices[i]}
TODO：还是没有完全理解
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int buy1 = -prices[0];
int sell1 = 0;
int buy2 = -prices[0];
int sell2 = 0;
for (int i = 1; i < n; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
题解思路2：设置多个状态位
所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][2][3];
int MIN_VALUE = Integer.MIN_VALUE / 2;
dp[0][0][0] = 0;//第一天休息
dp[0][0][1] = dp[0][1][1] = MIN_VALUE;//不可能
//dp[0][0][2] = dp[0][1][2] = MIN_VALUE;//不可能
dp[0][1][0] = -prices[0];//买股票
for (int i = 1; i < n; i++) {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][1][0] + prices[i]);
dp[i][0][2] = Math.max(dp[i - 1][0][2], dp[i - 1][1][1] + prices[i]);
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][0][0] - prices[i]);
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][1] - prices[i]);
}
return Math.max(0, Math.max(dp[prices.length - 1][0][1], dp[prices.length - 1][0][2]));
}
}
注：这里的初始化值不可以为0，而应该是一个无法取到的负值。否则在买入的判断中，永远无法买入。
188. 买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1： 输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。 |
|---|
题解思路：大体上的思路仍然和题123一样，只是状态位多了而已，转换状态是一样的。
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length==0||prices==null)
return 0;
int n = prices.length;
int[][][] dp = new int[n][2][k+1];
int MIN_VALUE = Integer.MIN_VALUE / 2;
dp[0][0][0] = 0;//第一天休息
for(int i=1;i<k;i++){
dp[0][0][i]= MIN_VALUE;
dp[0][1][i]= MIN_VALUE;
}
//dp[0][0][1] = dp[0][1][1] = MIN_VALUE;//不可能
//dp[0][0][2] = dp[0][1][2] = MIN_VALUE;//不可能
dp[0][1][0] = -prices[0];//买股票
for (int i = 1; i < n; i++) {
for(int j=0;j<=k;j++){
if(j==0)
dp[i][0][j] = dp[i - 1][0][j];
else{
dp[i][0][j] = Math.max(dp[i - 1][0][j], dp[i - 1][1][j-1] + prices[i]);
}
dp[i][1][j] = Math.max(dp[i - 1][1][j], dp[i - 1][0][j] - prices[i]);
}
}
int max=0;
for(int i=0;i<=k;i++){
max=Math.max(max,dp[prices.length-1][0][i]);
}
return max;
}
}
若有收获，就点个赞吧
0 人点赞
