1、动态规划：每一个状态一定是由之前的状态推导出来的，通过总结归纳发现递推关系
2、解决动态规划问题的步骤：
- 确定dp数组（dp table）以及下标的含义：? ?
- 每个单元内 题目所求的值，一维、二维
- 确定递推公式：? ? ?
- 当前元素面临的情况（是否相等、是否可选），每种情况下的可能取值，其中选择符合题意的
- dp数组如何初始化：
- 根据初始状态下dp矩阵的含义设置，且不能影响后续的计算
- 确定遍历顺序（根据递推公式，右侧表达式中值需优先计算）：
- 根据递推公式中索引的变化顺序（小到大，大到小），同步
- 举例推导dp数组，判断思路是否正确。
目录
6.1 成对/分成两个子集：求和/2，使得各子集趋近目标值（背包总含量），进行动态规划
6.2 组合问题: 求组合个数：动态规划，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]]； 求所有组合列表：回溯算法
6.4 完全背包：物品可多次添加，嵌套顺序均可，小到大（遍历顺序不同，01背包：先物品，在背包大到小）
8、股票获取最大收益：写出所有状态下? ?的所有情况下的收益取最大值，用数组存储
10. 子序列问题：公共序列（个数），或变为相等字符串（操作数），二维
3. 步骤示例：
示例：509. 斐波那契数
class Solution {
public int fib(int n) {
if(n <= 1) return n;//考虑特殊情况
int[] F = new int[n+1];//确定dp数组
F[0] = 0;//初始化dp
F[1] = 1;
for(int i = 2; i <= n; i++){//确定遍历顺序
F[i] = F[i-1] + F[i-2];//确定递推表达式
}
return F[n];
}
}
70. 爬楼梯 到n 阶有多少种方法
class Solution {
public int climbStairs(int n) {
if( n <= 2) return n;
int[] dp = new int[n+1];//n阶楼梯,存放n+1个数据，到每层个有多少种方法
//每次你可以爬 1 或 2 个台阶
dp[1] = 1;//只能一步
dp[2] = 2;//两个一步，或者，一个两步
//当前方法数 = dp[n-1] + dp[n-2] 一步到位，两步到
for(int i = 3; i<=n; i++){
dp[i] = dp[i-1] +dp[i-2];
}
return dp[n];
}
}
class Solution {
//每次你可以爬 1 或 2 个台阶, 进阶为每次可爬1-m个台阶
public int climbStairs(int n) {
int[] dp = new int[n+1];
int m = 2;//设置可走步数
if(n == 1 || n == 2) return n;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
for(int j = 1; j <= m && i >= j; j++){
dp[i] += dp[i-j];
}
}
return dp[n];
}
//746.达到楼梯顶部的最低花费
class Solution {
// cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用,在尾处加一个0表示楼顶,
public int minCostClimbingStairs(int[] cost) {
if(cost == null || cost.length <= 1) return 0;
int[] dp = new int[cost.length+1];
//可选择向上爬一个或者两个台阶
dp[0] = cost[0];
dp[1] = cost[1];
for(int i = 2; i < cost.length+1; i++){
if(i == cost.length){
dp[i] = Math.min(dp[i-1],dp[i-2]) + 0;
}else{
dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i];//之前的最小消耗+当前需消耗值
}
}
return dp[cost.length];
}
}4、路径问题：所有可达到当前格点一步距离的路径数之和
62. 不同路径：每次只能向下或者向右移动一步。机器人试图达到网格的右下角
63. 不同路径 II：考虑网格中有障碍物。从左上角到右下角将会有多少条不同的路
三种方法：
- 递归，将路径比作N叉树进行 深度遍历，时间复杂度高，超出时间限制O（2^(N+M-1)-1)
- 数论（组合。排列），转化成数学问题，求解公式，注意数值精度和数值范围，防止溢出
- 动态规划，根据各节点之间的关系，逐步推到。
// 动态规划
class Solution {
// 1.确定dp数组（dp table）以及下标的含义：dp[m][n]到达当前网格的路径数，下标：坐标
// 2.确定递推公式：每次只能向下或者向右移动一步 dp[i][j] = dp[i-1][j] + dp[i][j-1]
// 3.dp数组如何初始化:不能后退 dp[0][j] =1,dp[i][0]=1,到达机器人所在行列只有一种路径，直走
// 4.确定遍历顺序 ： 需一直i-1和j-1, 由上至下层次遍历
// 5.举例推导dp数组，判断思路是否正确。
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int j = 0; j < n; j++) dp[0][j] = 1;
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
//考虑网格中有障碍物,求路径数
class Solution {
//网格中的障碍物和空位置分别用 1 和 0, 有障碍物则可到达该位置的路径为0
//机器人每次只能向下或者向右移动一步,
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
if(obstacleGrid[m-1][n-1] == 1) return 0;
//若第一行、列有障碍物，则行列中障碍物之后的格点均无法到达
for(int i = 0; i< m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
for(int i = 1; i< m; i++){
for(int j = 1; j< n; j++){
if(obstacleGrid[i][j] == 1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
//数论方法 组合问题，到达终点的步数为：n-1+m-1，其中m-1步是向下走的，可形成的组合数，即路径数量
class Solution {
public int uniquePaths(int m, int n) {
// int res = 1;
// double numerator = n+m-2 ,denominator = m-1;//分子：A(n+m-2)(m-1),分母：A(m-1)(m-1)
// for(int i = 0; i < m-1; i++){
// res *= numerator/denominator;//会出现小数,损失精度了
// numerator--;
// denominator--;
// }
double numerator = 1 ,denominator = m-1;//分子：A(n+m-2)(m-1),分母：A(m-1)(m-1)
for(int i = 0; i < m-1; i++){
numerator *= (n+m-2-i);
while(denominator > 0 && numerator % denominator == 0){//表示当前分子可整除分母，避免精度损失和栈溢出
numerator = numerator/denominator;
denominator--;
}
}
return (int)numerator;
}
}
// //递归，深度优先遍历,会超出时间限制
// class Solution {
// // 每次只能向下或者向右移动一步 , 即每个节点只有两个方向，将路径比作二叉树，寻找可到达终点即n+m-2层的叶子结点的路径个数
// public int uniquePaths(int m, int n) {
// return dfs(m-1,n-1,m,n);
// }
// public int dfs(int i, int j,int m, int n){
// if(i == 0 || j == 0) return 1;//到达（i，j)节点的路径只有一个
// return dfs(i-1,j,m,n) + dfs(i,j-1,m,n);
// }
// }
5、拆分问题: 难点—寻找递推关系，有哪些拆分情况？
343. 整数拆分：一个正整数?n?，将其拆分为?k?个?正整数?的和，使所有整数的乘积最大化
96. 不同的二叉搜索树: 由?n?个节点组成且节点值从?1?到?n?互不相同的?二叉搜索树?有多少种
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];//从0-n的所有最大拆分乘积
dp[2] = 1;
for(int i = 3; i< n+1;i++){ //计算从0-n的所有最大拆分乘积
for(int j = i-1; j>= 1; j--){
dp[i] = Math.max(j*(i-j),dp[i]);
dp[i] = Math.max(j*dp[i-j],dp[i]);//与当前已知乘积比较，取最大值
//拆分成两个j*(i-j)
//拆分成多个数 j*dp[i-j]
}
}
return dp[n];
}
}
//96. 不同的二叉搜索树
class Solution {
// 二叉搜索树：左小右大
// 有n节点，依次左右根节点，计算对应的二叉搜索树种类数，相加
// 每个节点的二叉搜索树种类数 = 左子树的种类数*右子树的种类数 排列
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++){ //根节点的值:节点值从 1 到 n 互不相同
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
}6、背包问题：解决方法
01背包：取与不取，每件物品只能用一次。物品在外由小到大、背包在内由大到小
完全背包：取几个（0-N），每件物品可用无数次。背包物品的遍历嵌套顺序均可，都是小到大
如果求组合数就是 外层for循环遍历物品，内层for遍历背包。
如果求排列数就是 外层for遍历背包，内层for循环遍历物品。
多重背包：不同物品数量不同。 1.将物品按数量展开成01背包，通过01背包2维遍历求解；2.物品在外由小到大、背包在内由大到小、物品数量由小到大。3维for遍历。
分组背包：按组进行选择，每组只能用一次
- 动态规划：取与不取，改变状态值取最大价值
- 二维dp数组：
- 定义数据矩阵：dp[i][j] : i 表示物品，j 表示背包容量
- 递归公式：背包余量足够时：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，不足则保持前一状态：dp[i - 1][j]。
- 初始化：背包容量j为0，价值总和一定为0，即dp[i][0] = 0。背包可放入编号0的物品，则dp[0][j] = value[0]; 背包容量比编号0的物品重量还小，背包不能容纳任何物品，总价值为0, 即dp[0][j] = 0。并保证其他dp元素的初始值不影响 取最大值的运算，即取整数最小值或0；
- 遍历顺序：物体 和 背包 均正序遍历
- 一维dp数组：? 空间复杂度更低，简洁
- 定义数据矩阵：dp[j] :j 表示背包容量
- 递归公式：背包余量足够时：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，不足则保持前一状态：dp[j] ,不变。
- 初始化：背包容量j为0，价值总和一定为0，即dp[0] = 0。
- 遍历顺序：先正序遍历物品、在遍历背包容量，且背包容量一定是要倒序遍历，需要保证左边的值仍然是上一层的，从右向左覆盖。即保证物品i只被放入一次，只要当前背包余量容量可以放入该物品便放入
- 回溯法（即暴力解法）寻找所有状态，则n个物品取或不取，对应的时间复杂度就是$o(2^n)$
背包递推公式：
- 能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); dp总容量
- 装满背包有几种方法：dp[j] += dp[j - nums[i]] ；dp方法数
- 背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); dp总价值
- 装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);? dp元素数量
示例：
来自https://www.programmercarl.com/
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagsize = 4;
testweightbagproblem(weight, value, bagsize);
}
//一维dp
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++){
for (int j = bagWeight; j >= weight[i]; j--){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
//二维dp
public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
int wlen = weight.length, value0 = 0;
//定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
int[][] dp = new int[wlen + 1][bagsize + 1];
//初始化：背包容量为0时，能获得的价值都为0
for (int i = 0; i <= wlen; i++){
dp[i][0] = value0;
}
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 1; i <= wlen; i++){
for (int j = 1; j <= bagsize; j++){
if (j < weight[i - 1]){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
}
}
}
//打印dp数组
for (int i = 0; i <= wlen; i++){
for (int j = 0; j <= bagsize; j++){
System.out.print(dp[i][j] + " ");
}
System.out.print("\n");
}
}背包 例题：
6.1 成对/分成两个子集：求和/2，使得各子集趋近目标值（背包总含量），进行动态规划
416. 分割等和子集：将数组分割成两个子集，使得两个子集的元素和相等。
1049. 最后一块石头的重量 II：对一组石头进行对消粉碎，返回此石头?最小的可能重量
416. 分割等和子集
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
int target = 0;
for(int i = 0; i< nums.length; i++){
sum += nums[i];
}
if(sum % 2 != 0) return false;//和为奇数不可拆分
target = sum/2;//分割成两个子集,两个子集的元素和相等
// 0-1背包
int[] dp = new int[target+1];
dp[0] = 0;
for(int i = 0; i< nums.length; i++){
for(int j = target; j >= nums[i]; j--){
dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
}
}
//若存在一个子集的和值 = 总和的一半，剩余子集的和值也= 总和一半，满足题意
return dp[target] == target;
}
}
1049. 最后一块石头的重量 II
class Solution {
// 最小差值，最多只会剩下一块 石头
// 不限制粉碎次数，则 只要将石头分成两份，使得两份的差值尽可能小，即越接近总重/2 差值越小
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int i = 0; i< stones.length; i++){
sum += stones[i];
}
int target = sum/2;
int[] dp = new int[target+1];
dp[0] = 0;
for(int i = 0; i< stones.length; i++){
for(int j = target; j >= stones[i]; j--){
dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
}
}
return sum-dp[target]-dp[target];//sum-dp[target]表示另一集合的总重量
}
}6.2 组合问题: 求组合个数：动态规划，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]]； 求所有组合列表：回溯算法
动态规划
class Solution {
//向数组中的每个整数前添加 '+' 或 '-',即分成两组，一组取正值，一组取负值
// a-b = target a+b = sum ,a = (sum+target)/2
//返回 运算结果等于 target 的不同 表达式 的数目。
// 装满有几种方法: 组合问题 dp[j] += dp[j - nums[i]] dp[j]中存储的是装满j容量的方法数
//当前和的组成方法数 = 放入当前值后，和-当前值 的组成方法数
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i = 0; i< nums.length; i++){
sum += nums[i];//nums[i]全》=0
}
if(sum < Math.abs(target)) return 0;//-1000 <= target <= 1000
if( (sum+target) % 2 != 0) return 0;
int[] dp = new int[(sum+target)/2+1]; //存放 当前容积有多少种存放方法
dp[0] = 1;
for(int i = 0; i< nums.length; i++){//依次不同大小的背包中放入物品
for(int j = (sum+target)/2; j >= nums[i]; j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[(sum+target)/2];
}
}6.3 二维的01背包：即需要满足两个条件
474. 一和零：找出并返回?二进制字符串数组?strs?的最大子集的长度，该子集中?最?有?m个?0和?n个?1?。
class Solution {
//该子集中 最多 有 m 个 0 和 n 个 1 。
//找出并返回 strs 的最大子集的长度
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];//各条件下最大子集的长度
for(String s:strs){
int zeronum = 0, onenum = 0;
for(int i = 0; i< s.length(); i++){
if(s.charAt(i) == '0') {
zeronum ++;
}else{
onenum++;
}
}
//01背包，每个元素：放与不放，不放原值dp[i][j],放1+dp[i-zeronum][j-onenum];
for(int i = m; i >= zeronum; i--){
for(int j = n; j >= onenum; j--){
dp[i][j] = Math.max(dp[i][j], 1+dp[i-zeronum][j-onenum]);
}
}
}
return dp[m][n];
}
}6.4 完全背包：物品可多次添加，嵌套顺序均可，小到大（遍历顺序不同，01背包：先物品，在背包大到小）
- 01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。二维dp两个for循环嵌套顺序同样无所谓, 一维先物品在背包
- 完全背包的物品是可以添加多次的，所以要从小到大去遍历，两个for循环嵌套顺序无所谓
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}6.5 求装满背包有几种方案：
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。确保物品存取顺序不会颠倒。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
518. 零钱兑换 II:?返回可以凑成总金额的硬币组合数
377. 组合总和 Ⅳ：从?nums?中找出并返回总和为?target?的元素组合的个数。顺序不同的序列被视作不同的组合 == 排列数
322. 零钱兑换：最少的硬币个数 ，最少元素数
279. 完全平方数：返回 和为 n 的完全平方数的最少数量 ，最少元素数
139. 单词拆分：判断是否可以利用字典中出现的单词拼接出?s。判断是否可以装满背包
求组合数
518. 零钱兑换 II
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i = 0; i< coins.length; i++){
for(int j = coins[i]; j<= amount; j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}
求排列数
377. 组合总和 Ⅳ
class Solution {
//从 nums 中找出并返回总和为 target 的元素组合的个数。
//顺序不同的序列被视作不同的组合。
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;//和为0 的组合数：1
for(int i= 0; i <= target; i++){
for(int j = 0; j < nums.length; j++){
if(i >= nums[j]){
dp[i] += dp[i-nums[j]];
}
}
}
return dp[target];
}
}
322. 零钱兑换：最少的硬币个数
class Solution {
//计算并返回可以凑成总金额所需的 最少的硬币个数, 无则返回-1
//每种硬币的数量是无限的。 完全背包, 元素数量问题：组合排列都可以
public int coinChange(int[] coins, int amount) {
if(coins.length == 1 && amount % coins[0] != 0) return -1;//无法构成
int[] dp = new int[amount+1];// 存放凑成各金额所需的 最少的硬币个数
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 0; i < coins.length ; i++){
for(int j = coins[i]; j <= amount; j++){
if(dp[j-coins[i]] != Integer.MAX_VALUE){
dp[j] = Math.min(dp[j-coins[i]]+1,dp[j]);
}
}
}
return dp[amount] == Integer.MAX_VALUE? -1: dp[amount];
}
}
279. 完全平方数: 求元素最少个数
class Solution {
//返回 和为 n 的完全平方数的最少数量 。
//完全平方数 是一个整数，其值等于另一个整数的平方,eg:1、4、9 和 16
//可重复选取：完全背包
public int numSquares(int n) {
int[] dp = new int[n+1]; //组成和为n的完全平方数的最小数量
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
//先背包，后物品
// for(int i = 1; i <= n; i++){
// for(int j = 1; j*j <= i;j++){
// if(dp[i-j*j] != Integer.MAX_VALUE){
// dp[i] = Math.min(dp[i], dp[i-j*j]+1);
// }
// }
// }
// 先物品，后背包
for(int i = 0; i <= Math.sqrt(n); i++){
for(int j = i*i; j <= n; j++){
if(dp[j - i*i] != Integer.MAX_VALUE){
dp[j] = Math.min(dp[j - i*i] + 1, dp[j]);
}
}
}
return dp[n] == Integer.MAX_VALUE? -1:dp[n];
}
}
139. 单词拆分:s是否可以装满背包
// class Solution {
// //不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 即：完全背包
// //判断是否可以利用字典wordDict中出现的单词拼接出 s
// //s:背包 wordDict：物品
// //递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
// public boolean wordBreak(String s, List<String> wordDict) {
// boolean[] dp = new boolean[s.length()+1];//存放，当前位置之前的全部元素是否已可由字典组成。
// dp[0] = true;//0下标表示没有元素null
// for(int i = 1; i <= s.length(); i++){
// for(int j = 0; j < i; j++){//截取字符串，判断是否存在字典中
// String str = s.substring(j,i);
// if(wordDict.contains(str) && dp[j] == true){
// dp[i] = true;
// }
// }
// }
// return dp[s.length()];
// }
// }
// 回溯法+记忆化
class Solution {
int[] flag ;
public boolean wordBreak(String s, List<String> wordDict) {
flag = new int[s.length()];
return backtracking(s,0,wordDict);
}
public boolean backtracking(String s, int index, List<String> wordDict){
if(index == s.length()){
return true;//已经寻找结束，前面的已完全匹配
}
if(flag[index] == -1){
return false;//flag中元素表示，从index开始向后匹配能否匹配成功，不能则直接结束
}
for(int i = index; i < s.length(); i++){
String str = s.substring(index,i+1);//截取子字符串，左闭右开
if(wordDict.contains(str)){
boolean res = backtracking(s, i+1, wordDict);
if(res) return true;
}
}
//到这,表示以改坐标为起点，匹配不成功，标记并返回
flag[index] = -1;
return false;
}
}7、不同的数据结构类型，如何进行动态规划
198. 打家劫舍：队列排列，两间相邻的房屋不能同时进入，求可偷窃到的最高金额。?Math.max(dp[i-2]+nums[i], dp[i-1])，偷、不偷，取较大值
213. 打家劫舍 II：环状排列，两间相邻的房屋不能同时进入+首尾房间紧挨着。首尾不能同时可选，分两种情况：头可选、尾可选 ，分别计算 取两者的较大值
337. 打家劫舍 III：二叉树排列，一个入口，每个房子有且仅有一个父房子，两间直接相连的房屋不能同时进入。树状结构：后序遍历 + 二维数组标记左右节点状态与值，根据父节点状态取值
198. 打家劫舍
class Solution {
//不可取 两间相邻的元素,所以每次至少走2步
//偷窃到的最高金额。
public int rob(int[] nums) {
if(nums.length == 1) return nums[0];
int[] dp = new int[nums.length];//存放总金额
dp[0] = nums[0];//偷时金额为0
dp[1] = Math.max(nums[0],nums[1]);
//影响dp[i]的因素是，i房屋偷不偷，
//偷dp[i] = nums[i]+dp[i-2],i+1不可偷;不偷，dp[i] = dp[i-1]，i+1可偷;
for(int i = 2; i < nums.length; i++){
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[nums.length-1];
}
}
213. 打家劫舍 II
class Solution {
//所有的房屋都 围成一圈 第一个房屋和最后一个房屋是紧挨着的:不能同时可取 分两种情况考虑
//两间相邻的房屋不能同时进入
//求偷窃到的最高金额 dp
public int rob(int[] nums) {
if(nums.length == 1) return nums[0];
int res1 = robRange(nums, 0, nums.length-1);//考虑头元素，不取尾
int res2 = robRange(nums, 1, nums.length);//考虑尾元素 ，不取头
return Math.max(res1, res2);
}
public int robRange(int[] nums, int start, int end){//左闭右开
int[] dp = new int[nums.length];
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]);//第i个房间偷不偷
}
return dp[end-1];
}
}
337. 打家劫舍 III
//从叶子结点开始遍历,后序遍历
// 当前节点i 偷不偷，偷，i-2层的数组和，左左，左右，右左，右右+value, 不偷，dp[i] = dp[i].left+dp[i].right
class Solution {
Map<TreeNode,Integer> map = new HashMap<>();//记录每个节点的最大金额，没有记录每个节点的状态（偷没偷）
public int rob(TreeNode root) {
if(root == null) return 0;
if(map.containsKey(root)) return map.get(root);
//偷root节点
int res1 = root.val;
if(root.left != null){
res1 += rob(root.left.left) + rob(root.left.right);
}
if(root.right != null){
res1 += rob(root.right.left) + rob(root.right.right);
}
//不偷root节点
int res2 = rob(root.left) + rob(root.right);
int val = Math.max(res1,res2);
map.put(root,val);
return val;
}
}
// 记录每个节点的状态（偷 / 没偷）以及对应最大金额，返回值为int[2]类型;
// 不偷：Max(左孩子不偷，左孩子偷) + Max(又孩子不偷，右孩子偷)
// root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
// Math.max(rob(root.right)[0], rob(root.right)[1])
// 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
// root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
class Solution {
public int rob(TreeNode root) {
int[] res = robTree(root);
return Math.max(res[0], res[1]);//0没偷，1偷了
}
public int[] robTree(TreeNode root){
if(root == null) return new int[]{0,0};//相当于初始化
int[] res = new int[2];
int[] left = robTree(root.left);
int[] right = robTree(root.right);//不要在下面的表达式中直接写，会多次重复运算
res[0] = 0 + Math.max(left[0], left[1])
+ Math.max(right[0], right[1]);
res[1] = root.val +left[0] +right[0];
return res;
}
}8、股票获取最大收益：写出所有状态下? ?的所有情况下的收益取最大值，用数组存储
- dp[i][0] 表示第i天持有股票所得现金。
- dp[i][1] 表示第i天不持有股票所得最多现金
121. 买卖股票的最佳时机：只能选择某天买进，之后的某天卖出，取最大利润
股票全程只能买卖一次：(贪心：左最低买入，右最高卖出）两种状态
- 第i天不持有股票：1、之前卖出dp[i-1][1]? 2、当天卖出则第i-1天持有dp[i-1][0]+price[i]
- 第i天持有股票：1、之前也持有dp[i-1][0]? 2、当天持有的 -price[i]
股票全程能买卖多次：（贪心：取所有正收益的和）两种状态：延续，改变状态
- 第i天不持有股票：1、之前卖出dp[i-1][1]? 2、当天卖出则第i-1天持有dp[i-1][0]+price[i]
- 第i天持有股票：1、之前也持有dp[i-1][0]? 2、当天持有的，之前的盈利(即i-1天不持有）减支出?dp[i-1][1]-price[i]
股票最多可以买卖两次：5种状态
股票最多可以买卖K次：2*k+1种状态，即0:无操作，奇数：买入 -prices，偶数：卖出 +prices
309. 最佳买卖股票时机含冷冻期：买入时? 跳过冷冻期时间取之前卖出收益
714. 买卖股票的最佳时机含手续费：买入时有手续费：买入时 当前收益-股价-手续费
121. 买卖股票的最佳时机
class Solution {
//贪心算法，取最小买入价格，最高收益，效率更高
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int res = 0;//记录最大利润
for(int i = 0; i< prices.length; i++){
min = Math.min(min,prices[i]);//取最低买入金额
res = Math.max(res,prices[i] - min);//之前卖出，和 当前卖出 取较大值
}
return res;
}
}
class Solution {
//动态规划，每日更新
public int maxProfit(int[] prices) {
int[] dp = new int[2];//0:持有（当天买入、之前买入） ，1:不持有（卖出，之前卖出）
//dp存放获得最大收益
dp[0] = -prices[0];
dp[1] = 0;
for(int i = 1; i < prices.length; i++){
dp[0] = Math.max(dp[0],-prices[i]);
dp[1] = Math.max(dp[1], prices[i]+dp[0]);//当天卖出，前一天一定是持有的
}
return dp[1];//卖出，收益更高
}
}
122. 买卖股票的最佳时机 II
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][2];//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(prices[i]+dp[i-1][0], dp[i-1][1]);
}
return dp[len-1][1];
}
}
123. 买卖股票的最佳时机 III
class Solution {
//你最多可以完成 两笔 交易。
public int maxProfit(int[] prices) {
int[] dp = new int[5];//有5种状态下的收益
dp[0] = 0;//无操作
dp[1] = -prices[0];//第一次买入
dp[2] = 0;//第一次卖出
dp[3] = -prices[0];//第二次买入
dp[4] = 0;//第二次卖出
for(int i = 1; i < prices.length; i++){
//后面的状态需要前面的值，从4-》0更新状态收益
dp[4] = Math.max(dp[4], dp[3]+prices[i]);//延续，或当天改变状态
dp[3] = Math.max(dp[3], dp[2]-prices[i]);
dp[2] = Math.max(dp[2], dp[1]+prices[i]);
dp[1] = Math.max(dp[1], dp[0]-prices[i]);
dp[0] = 0;
}
return dp[4];//最后的卖出状态收益更高
}
}
188. 买卖股票的最佳时机 IV:最多可以完成 k 笔交易。
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices == null || prices.length == 0) return 0;
int[] dp = new int[2*k+1];
dp[0] = 0;
for(int j = 1; j < 2*k+1; j = j+2){
dp[j] = -prices[0];
}
for(int i = 1; i < prices.length; i++){
for(int j = 2*k; j > 0; j--){
int sign = (j%2==0? 1:-1);//奇数买入，偶数卖出
dp[j] = Math.max(dp[j],dp[j-1]+sign*prices[i]);
}
}
return dp[2*k];
}
}
309.最佳买卖股票时机含冷冻期
class Solution {
//卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
//尽可能地完成更多的交易（多次买卖一支股票）
public int maxProfit(int[] prices) {
if(prices == null || prices.length <= 1) return 0;
//状态：0买入（第i天买入的话之前的收益为i-2天的卖出状态的收益），1卖出
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[1][0] = Math.max(dp[0][0],-prices[1]);
dp[1][1] = Math.max(prices[1]+dp[0][0],0);
for(int i = 2; i < prices.length; i++){
dp[i][0] = Math.max(dp[i-1][0], dp[i-2][1]-prices[i]);//买入状态
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);//卖出状态
}
return dp[prices.length-1][1];
}
}
714. 买卖股票的最佳时机含手续费
class Solution {
public int maxProfit(int[] prices, int fee) {
// int[][] dp = new int[prices.length][2];//0买入，1卖出
// dp[0][0] = -prices[0]-fee;
// dp[0][1] = 0;
// for(int i = 1; i< prices.length; i++){
// dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]-fee);
// dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);
// }
// return dp[prices.length-1][1];
int[] dp = new int[2];//0买入，1卖出
dp[0] = -prices[0]-fee;
dp[1] = 0;
for(int i = 1; i< prices.length; i++){
dp[0] = Math.max(dp[0], dp[1]-prices[i]-fee);
dp[1] = Math.max(dp[1], dp[0]+prices[i]);
}
return dp[1];
}
}9、子序列问题：单一维度
- dp[i]? 存储到当前值满足条件的最大长度、个数，取dp中的最大值
- dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。根据变化条件（一般为当前相应值是否相等）相等则不变，取斜上角值（二维）、前一个值（一维）+增量；不等 取周边最大值最小值+增量
300. 最长严格递增子序列：j = 0~i? ? ?nums[i] > nums[j]则?dp[i] = max(dp[i], dp[j] + 1);即长度+1674. 最长连续递增序列：nums[i]>nums[i-1] 则 dp[i]?=?Math.max(dp[i],dp[i-1]+1)
53. 最大连续子数组和:? 贪心（只取连续子列的正和，否则为0以当前元素从新开始）、动态规划（求当前位置i的最大连续子数组和：dp[i]?=?Math.max(dp[i-1]+nums[i],?nums[i]) 取所有dp的最大值）
300. 最长递增子序列
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];//记录以nums[i]为结尾的子序列的最长递增子序列的长度
int res = 1;
Arrays.fill(dp,1);//递增子序列的最小长度为1
for(int i = 1; i< nums.length; i++){
for(int j = 0; j< i; j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[i], dp[j]+1);//当前数值为结尾的递增子序列的最大长度+1
}
}
res = Math.max(dp[i],res);//取最大值
}
return res;
}
}
674. 最长连续递增序列
class Solution {
//最长且 连续递增的子序列
public int findLengthOfLCIS(int[] nums) {
//动态规划
// int[] dp = new int[nums.length];
// int res = 1;
// Arrays.fill(dp,1);
// for(int i = 1; i< nums.length; i++){
// if(nums[i]>nums[i-1]){//连续
// dp[i] = Math.max(dp[i],dp[i-1]+1);//存储到当前值的最大长度
// }
// res = Math.max(dp[i],res);
// }
// return res;
//贪心算法，更快
int count = 1; //记录递增长度
int res = 1; //记录最大长度
for(int i = 1; i< nums.length; i++){
if(nums[i]>nums[i-1]){
count++;
}else{
count = 1;
}
res = Math.max(res,count);
}
return res;
}
}
53. 最大子数组和
class Solution {
public int maxSubArray(int[] nums) {
// 贪心算法，支取正和区间
// if(nums.length == 1) return nums[0];
// int res = Integer.MIN_VALUE;
// int sum = 0;
// for(int i= 0; i< nums.length; i++){
// if(sum < 0){
// sum = 0;//之前元素的和为负数，则不取
// }
// sum += nums[i];
// res = Math.max(sum,res);
// }
// return res;
//动态规划 dp[i] 0-i的子序列的最大和
int[] dp = new int[nums.length];
dp[0] = nums[0];
int res = dp[0];
for(int i=1; i< nums.length; i++){
dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);//看之前取的元素和是正还是负
res = res > dp[i]? res: dp[i];//取所有最大和的最大值
}
return res;
}
}
10. 子序列问题：公共序列（个数），或变为相等字符串（操作数），二维
重点：1. dp矩阵的定义，2. 当前元素存在的几种情况和相应的操作? 对dp元素值的影响
718. 最长重复子数组: 求两个数组的最大重复子序列长度，二维遍历比较，相同+1。
- 二维dp记录每个位置上可取的最大公共子序列长度。行：nums1元素i，列：nums2元素j，对应i/j元素相同：dp[i+1][j+1] = dp[i][j]+1;
- 一维dp :类似背包，一个数组为物品i，另一个为背包容器j，判断背包中是否含有该物品，相同则dp[i] = dp[j-1]+1，不同则dp[i] = 0;
1143. 最长公共子序列: 求两个字符串的 最大公共子序列长度（即相对位置保持一致），二维遍历，相同则+1（dp[i-1][j-1]+1）,不同取相邻位置的较大值max(dp[i-1][j],dp[i][j-1]).
1035. 不相交的线:? 连接两个数组中的相同元素，保证连线之间不相交，求绘制的最大连线数 = 元素的相对位置保持一致，求最大公共子序列长度。与上题一致。
392. 判断子序列: 判断 s 是否为 t 的子序列， 即s和t的最大公共子序列的长度是否等于s的长度。（直接向后查询所需元素，或者双指针法比较元素 均可解出）
if (s[i - 1] == t[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + 1; //t中找到了一个字符在s中也出现了
}else {
dp[i][j] = dp[i][j - 1];//相当于t要删除元素，继续匹配
}115. 不同的子序列:计算在 s 的子序列中 t 出现的个数。(元素的相对位置相同）。
判断当前元素是否对应相等，相等叠加;，不等保持 ;
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
//相等 时? =?当前包含s[i-1]元素时+?不包含s[i-1]元素时?t(0-j-1子序列)的出现个数?
} else {
dp[i][j] = dp[i - 1][j];
//不相等时? = 不包含s[i-1]元素时?t(0-j-1子序列)的出现个数
}583. 两个字符串的删除操作: 两个字符串只能删除元素，使得 二者相同所需的最小步数。
对应元素相等，操作数不增加； 不相等，删除w1元素，对应位置操作数的基础上+1，删除w2元素，操作数+1；l两者都删除，操作数+2；
72. 编辑距离: 对字符串进行插/删除/替换字符操作，变成目标字符串，最少需要多少操作数。
dp[i][j]:表示s1的0~i-1和s2的0~j-1的编辑距离
if (word1[i - 1] == word2[j - 1])
dp[i][j] = dp[i - 1][j - 1];//不操作
if (word1[i - 1] != word2[j - 1])
dp[i][j] = dp[i - 1][j] + 1;//增
dp[i][j] = dp[i][j - 1] + 1;//删
dp[i][j] = dp[i - 1][j - 1] + 1;//换
//三种情况中选一个
//题目要求：最小操作数：取三者最小值718. 最长重复子数组
class Solution {
public int findLength(int[] nums1, int[] nums2) {
// int[][] dp = new int[nums1.length+1][nums2.length+1];
// //dp[i][j] 表示nums1 0~i-1处 与nums2 0~j-1处的公共序列长度
// //dp[i][0] = 0; dp[0][j] = 0;均表示未取值
// int res = 0;
// for(int i = 0; i< nums1.length; i++){
// for(int j = 0; j< nums2.length; j++){
// if(nums1[i] == nums2[j]){
// dp[i+1][j+1] = dp[i][j]+1;
// res = Math.max(dp[i+1][j+1],res);//保存最大值
// }
// }
// }
// return res;
//将二维变为一维, 向下对角线上元素相等+1
int[] dp = new int[nums2.length+1];
int res = 0;
//类似背包
for(int i = 0; i < nums1.length; i++){//物品
for(int j = nums2.length-1; j>=0; j--){//背包 从后向前遍历，避免重复
if(nums1[i] == nums2[j]){
dp[j+1] = dp[j]+1;
}else{
dp[j+1] = 0;//当前数值不相等，表示以当前数值为结尾的序列是不存在公共序列的
}
res = Math.max(dp[j+1],res);
}
}
return res;
}
}
1143. 最长公共子序列
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
if(text1 == null || text2 == null || text1.length() == 0|| text2.length() == 0){
return 0;
}
char[] t1 = text1.toCharArray();
char[] t2 = text2.toCharArray();
//二维dp
int[][] dp = new int[t1.length+1][t2.length+1];
//dp[i][j] : text1的0~i-1的子序列与 text2的0~j-1的子序列 的最大公共子序列的长度
//第0行、0列均为0， 列text2元素，行text1元素
for(int i = 1; i <= t1.length; i++){
for(int j = 1; j<= t2.length; j++){
if(t1[i-1] == t2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;//相等+1
}else{
dp[i][j]= Math.max(dp[i-1][j],dp[i][j-1]);//不等取最大值
}
}
}
return dp[t1.length][t2.length];
}
}
}
392. 判断子序列:判断 s 是否为 t 的子序列。
class Solution {
public boolean isSubsequence(String s, String t) {
if(s == null || t == null || s.length() > t.length()){
return false;
}//特殊情况判断
int index = -1;
for(char c : s.toCharArray()){
index = t.indexOf(c,index+1);
if(index == -1) return false;//没找到该元素
}
return true;
//双指针法
int si = 0;
int ti = 0;
while(si < s.length() && ti < t.length()){
if(s.charAt(si) == t.charAt(ti)){
si++;
}//当前元素以匹配，后移指针
ti++;
}
return si == s.length();
//动态规划：s 为 t 的子序列即 s/t最大公共子序列的长度为s的长度
int[][] dp = new int[s.length()+1][t.length()+1];
//dp[i][j] : 表示s的0~i-1 与t的0~j-1的相同子序列的长度
char[] s1 = s.toCharArray();
char[] t1 = t.toCharArray();
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= t.length(); j++){
if(s1[i-1] == t1[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = dp[i][j-1];//dp[i-1][j] 一定比dp[i][j-1]小，因为 t1[j-1]无用
}
}
}
return dp[s.length()][t.length()] == s.length();//最大公共子序列的长度为s的长度
}
}
115. 不同的子序列:计算在 s 的子序列中 t 出现的个数。(元素的相对位置相同）
class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[s.length()+1][t.length()+1];
//dp:在 s 的子序列中 t 出现的个数。dp[0][j] = 0,s为[],不可能包含t
for(int i = 0; i < s.length(); i++){
dp[i][0] = 1;//即t为空[]
}
char[] s1 = s.toCharArray();
char[] t1 = t.toCharArray();
for(int i = 1; i<= s.length(); i++){
for(int j = 1; j <= t.length(); j++){
//延续 或 叠加
if(s1[i-1] == t1[j-1]){
//相等 = 当前包含s[i-1]元素时+ 不包含s[i-1]元素时 t(0-j-1子序列)的出现个数
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j];//不包含s[i-1]元素时 t(0-j-1子序列)的出现个数
}
}
}
return dp[s.length()][t.length()];
}
}
72. 编辑距离
class Solution {
public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();
int[][] dp = new int[l1+1][l2+1];
char[] w1 = word1.toCharArray();
char[] w2 = word2.toCharArray();
//初始化，字符串《-》空集 的操作数 = 元素数
for(int i = 0; i <= l1; i++){
dp[i][0] = i;
}
for(int j = 0; j <= l2; j++){
dp[0][j] = j;
}
for(int i = 1; i <= l1; i++){
for(int j = 1; j <= l2; j++){
if(w1[i-1] == w2[j-1]){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
//dp[i-1][j]+1 :w2添加元素 即添加w1[i-1]元素
//dp[i][j-1]+1 : W2删除w2[j-1]元素
//dp[i-1][j-1]+1 :w2替换
}
}
}
return dp[l1][l2];
}
}
583. 两个字符串的删除操作
class Solution {
public int minDistance(String word1, String word2) {
int l1 = word1.length();
int l2 = word2.length();
char[] w1 = word1.toCharArray();
char[] w2 = word2.toCharArray();
//方式一：求两个字符串的公共序列长度，再用各自字符串长度- 公共序列长度
//方式二：直接统计使得当前子序列相等 的最小步数
int[][] dp = new int[l1+1][l2+1];//子序列相等 的最小步数
// 要与空集相等的最小步数 = 序列长度
for(int i = 0; i <= l1; i++){
dp[i][0] = i;
}
for(int j = 1; j <= l2; j++){
dp[0][j] = j;
}
for(int i = 1; i <= l1; i++){
for(int j = 1; j <= l2; j++){
if(w1[i-1] == w2[j-1]){//相等，不操作
dp[i][j] = dp[i-1][j-1] ;
}else{//不相等，取当前最小步数
dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
//删除w1[i-1];删除w2[j-1];两个都删除；
}
}
}
return dp[l1][l2];
}
}11、回文字符串的判断、统计
647. 回文子串：统计并返回这个字符串中?回文子串?的数目，统计dp中为true的单元数
- dp[i][j]: 字符串i-j位置的序列是否为回文子串，true，false；根据定义：必须 j >= i
-
if (s[i] == s[j]) { if (j - i <= 1) { // 情况一 和 情况二 //下标相同或者相差为1，该字符串为回文子串 result++; dp[i][j] = true; } else if (dp[i + 1][j - 1]) { // 情况三 //相差> 1，需要判断他们的中间字符串是否是回文的 result++; dp[i][j] = true; //当前结果需要已知dp[i + 1][j - 1]，遍历顺序i:下到上，j:左到右 } }
516. 最长回文子序列: 找出其中最长的回文子序列按顺序选择的字符串）
dp[i][j]: 字符串i-j位置的子序列构成的回文子串的最大长度；；相等：数量+2，不等，取可能情况的最大值
647. 回文子串
//动态规划
class Solution {
public int countSubstrings(String s) {
int len = s.length();
char[] s1 = s.toCharArray();
boolean[][] dp = new boolean[len][len];//初始值false
int count = 0;
for(int i = len-1; i >= 0; i--){
for(int j = i; j < len; j++){
if(s1[i] == s1[j]){
if(j-i <= 1 || dp[i+1][j-1] == true){
dp[i][j] = true;
count++;
}
}
}
}
return count;
}
}
//双指针法，以对称中心（1个元素，2个元素）向两侧出发，比较对应元素
class Solution {
public int countSubstrings(String s) {
int count = 0;
char[] s1 = s.toCharArray();
for(int i = 0; i< s1.length; i++){
count += extend(i,i,s1);
count += extend(i,i+1,s1);
}
return count;
}
public int extend(int i, int j, char[] s){
int res = 0;
while(i >= 0 && j < s.length && s[i] == s[j]){//考虑边界
i--;
j++;
res++;
}
return res;
}
}
516. 最长回文子序列: 不改变剩余字符顺序的情况下，删除某些字符
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
char[] s1 = s.toCharArray();
int[][] dp = new int[len][len];//i-j的回文子序列的最长长度
int res = 0;
if(s == null || len == 0){
return res;
}else{
res = 1;
}
for(int i = 0; i < len; i++){
dp[i][i] = 1;//单个元素也是回文
}
for(int i = len-1; i >= 0; i--){
for(int j = i+1; j < len; j++){
if(s1[i] == s1[j]){
dp[i][j] = dp[i+1][j-1]+2;//i 大到小，j小到大
}else{
dp[i][j] = Math.max(Math.max(dp[i+1][j],dp[i][j-1]),dp[i+1][j-1]);
//不等时，删除左侧元素、还是右侧元素，还是两边都删除
}
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}