动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划问题五步曲：
1.确定dp数组（dp table）以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。
这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。
本质是最优化算法，目的都是求极值，方法核心是穷举。
动态规划解法代码框架
#初始化 base case
dp[o][o][...]= base
#进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值：
for
dp[状态1][状态2］[·.·］=求最值(选择1，选择2..·）
基础题目
509. 斐波那契数 最基础的
class Solution {
public int fib(int n) {
if (n < 2) return n;
int a = 0, b = 1, c = 0;
for (int i = 1; i < n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
70. 爬楼梯 依旧基础
和上一题差不多，就多了一个自定义数组初始化。
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
746. 使用最小花费爬楼梯 最小值问题
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp=new int[cost.length];//表示踏上第 i 级台阶时累计的最小花费
dp[0]=cost[0];
dp[1]=cost[1];
for(int i=2;i<cost.length;i++){
dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];//踏上台阶就算花费，预支付去下一层的花销
}
//最后一步，踏上倒数第二步的时候就已经支付过了到这步的花销
return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}
}
62. 不同路径 二维棋盘
二维棋盘，所以两个for遍历。
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp=new int[m][n];
//初始化
for(int i=0;i<m;i++){
dp[i][0]=1;
}
for(int i=0;i<n;i++){
dp[0][i]=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 二维棋盘+障碍物
比上一题多了限制：棋盘中有格子不能走。遍历的时候多个if判断。
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<m&&obstacleGrid[i][0]==0;i++){
dp[i][0]=1;
}
for(int i=0;i<n&&obstacleGrid[0][i]==0;i++){
dp[0][i]=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];
}
}
343. 整数拆分 求最大值
所有dp[i]都是题目所求。dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
不必想着罗列所有情况取最优，直接每次递推的时候都取最大值。
因为i拆成正整数之和相乘是dp[i]，所以有
dp[i]=dp[i-j]* j //把整数拆分成一系列的数相乘
或者是 (i-j) * j;//单纯的把整数拆分为两个数相乘
推出最终的递推方程
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
根据递推方程，所以是从前往后遍历。i和j都是自变量，所以双重for遍历。
i从2开始遍历，dp[2]初始化为1。题目提示说了n>=2。
j从1开始遍历，为了优化，j <= i / 2，因为拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。
class Solution {
public int integerBreak(int n) {
int[] dp=new int[n+1];//dpi就是i对应的最大乘积，所以长度是n+1
dp[2]=1;
for(int i=3;i<=n;i++){
for(int j=1;j<=n/2&&(i-j)>0;j++){
dp[i]=Math.max(dp[i],Math.max(dp[i-j]*j,(i-j)*j));
}
}
return dp[n];
}
}
96. 不同的二叉搜索树 组合问题
dpi是i个节点时可以组成的二叉搜素树的种类数。
树可以拆成子树，所以方便递推。
轮流寻找不同的点作为根节点。固定一个点，其他点变成子树，再固定住根节点。不同根节点的可能性肯定是相加的，左右子树的可能性是相乘的，因为左右子树其实是独立的，比如说左子树有2种可能性，右子树有三种可能性，那总可能性就是2 * 3=6。
对于每个 i，计算由 i 个节点组成的 BST 数量时，需要遍历所有可能的根节点 j（从 1 到 i），并将问题拆分为左子树（j-1 个节点）和右子树（i-j 个节点）
i子树中，j设为根节点，那么根据 二叉搜索左小右大，左子树的根节点就只能是1~j-1；右子树的根节点就只能是j+1~i；
以 j 为根的 BST 总数 = 左子树数量 × 右子树数量 = dp[j-1] * dp[i-j]
dp[i]=dp[j-1] * dp[i-j]+dp[i] dpi是j从1到i的和。
不理解递推的时候回头看看dp定义。
初始化：
dp[0] = 1（空树也算一种情况）。
dp[1] = 1（单节点只有一种 BST）
class Solution {
public int numTrees(int n) {
int[] dp=new int[n+1];//dpi是i个节点组成的最多树的可能性
dp[0]=1;
dp[1]=1;
//i个节点中，j轮流做根节点
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]=dp[i]+dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}
背包问题
总结 🍎
step1：检查物品选取规则
每个物品只能选一次？→ 0-1 背包（倒序）
可以无限选？→ 完全背包（正序）
每组只能选一个？→ 分组背包
一般dp数组初始化长度都是目标值加1；
step2.判断问题类型
1.组合数问题，目的是统计有多少种方式能凑出和 j。 “是否 / 方式数”
递推公式：dp[j] += dp[j - nums[i]]。
dp[j]定义是容量为j的背包有多少种可能性填满。
递推解释：递推也就变成 容量为j的背包填满的可能性是 不选当前数字num[i]填满的可能性（继承之前的dp[j]) + 选当前数字填满的可能性(背包容量j要减去num[i])。
初始化：dp[0] = 1
遍历顺序：先遍历物品i再背包j。
2.排列问题，也是统计多少种方式能凑出和j，但是组合之间有先后顺序。完全背包问题
和组合数问题的不同在于：
遍历顺序：先遍历背包j再遍历物品i。 因为先遍历物品就无法添加之前的物品。并且两个for里，i，j初始值都是0。
其余不变。
3.最值问题，目的是能凑出的最值和，只关心能否凑出某个和，而不关心有多少种凑法。 “凑出。。+最”
有两类问题：求最大值和最小值。
递推公式：Math.max(dp[j], dp[j - nums[i]] + nums[i])或者Math.min
dp[j]是容量为j的背包的价值总和是多少。
初始化： 最大值如果都是正整数之间讨论那就是全填充0；最小值全填充 Integer.MAX_VALUE。直接用Arrays.fill函数。
遍历顺序： 先从0开始遍历物品i，倒序遍历背包j。其中求最小值时，需先判断dp[j - nums[i]] != MAX_VALUE再转移
上面所有问题对于背包的遍历都是：
01背包：在遍历背包时是倒序的，以防止同一个物品被选多次。
完全背包：在遍历背包时是正序的，允许每个物品被选多次。（但如果是求最小数，那么两层for循环的先后顺序就无所谓了。）
和字符串结合： 遍历物品是for(String word:words) 字符串本身天然有顺序，如果是拆分这种，状态转移依赖于前驱状态的顺序（如 dp[j] 依赖 dp[j-len]），通常是排列问题；如果是子集或者统计出现频率就是组合问题。
细节：dp长度就是数组长度，初始化dp[0]就是结果值，for i< 数组长度就行了，返回的是 dp[数组长度-1]
dp长度是目标值+1,初始化dp[0]=1；for i<= 数组长度 ；返回的就是dp[目标值]；
什么时候用哪种？
用第一种：问题直接处理数组/字符串的每个元素，且 dp[i] 明确表示以 nums[i] 或 s[i] 结尾的状态。不需要处理空子问题。
用第二种：问题需要处理空子问题（如空字符串、空子序列）。
多重背包： 每种物品有固定数量限制 不是完全背包的无限次，也不是01背包的只能选一次。
其实就是多了一重for 物品次数的循环。其他一样和完全背包一样。
除了排序是正序遍历背包，其他都是逆序遍历背包。
除了排序是先遍历背包再物品再物品次数，其他都是先物品再背包最后物品次数。
1.组合问题（求方案数）逆序背包
public int combination(int[] nums, int target, int[] s) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= nums[i]; j--) { // 逆序
for (int k = 1; k <= s[i] && k * nums[i] <= j; k++) {
dp[j] += dp[j - k * nums[i]];
}
}
}
return dp[target];
}
2.排列问题（考虑顺序） **正序背包 **
public int permutation(int[] nums, int target, int[] s) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int j = 0; j <= target; j++) { // 先遍历容量
for (int i = 0; i < nums.length; i++) { // 再遍历物品
for (int k = 1; k <= s[i] && k * nums[i] <= j; k++) {
dp[j] += dp[j - k * nums[i]];
}
}
}
return dp[target];
}
3.最值问题 逆序背包
public int maxValue(int[] weights, int[] values, int[] s, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int j = capacity; j >= weights[i]; j--) { // 逆序
for (int k = 1; k <= s[i] && k * weights[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * weights[i]] + k * values[i]);
}
}
}
return dp[capacity];
}
1. 01背包 重要
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
因为有两个维度需要分别表示：物品 和 背包容量 ，所以使用二维数组:i 来表示物品、j表示背包容量 。dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
对于递推公式，首先我们要明确有哪些方向可以推导出dp[i][j]。
有两种情况，放物品i 和 不放物品i。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
不放物品i的话，当前价值就还是上一次的最大值。
放物品i的话，背包容量j要减去物品i的体积，当前价值是之前的最大价值加上i的价值，所以dp是i-1。
初始化：背包容量j为0，价值肯定也是0。i为0，也就是只能拿下标0的物品的时候，背包价值多少：当背包容量装不下0物品时，价值0；装的下时，价值就是物品0的价值。
从递归公式 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。
遍历顺序：根据递归公式发现需要的数据都在左上，所以先遍历谁都可以，但选择先遍历物品更好理解。
优化：滚动数组。将二维背包问题压缩至一维，前提是上一层可以重复利用，直接拷贝到当前层。
对于背包问题其实状态都是可以压缩的。
从二维递归公式可以知道需要用到 之前状态价值最大 当前物品重量 当前物品价值 这三个。
一维dp数组，其实就上上一层 dp[i-1] 这一层 拷贝的 dp[i]来。
一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
数组是一维的，但是变量还是两个，仍然是二重遍历，其实就是就是dp[i][j]中i的维度去掉了。
初始值设为0。
但是为了保证物品i只被放入一次，要倒序遍历。
再来看看两个嵌套for循环的顺序，必须是先遍历物品嵌套遍历背包容量。
比较：一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级。
416. 分割等和子集 最大值问题
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 ；数组的大小不会超过 200
step1分析：转化问题：找子集，和为总和的一半，从而变成 0−1 背包
回溯也能做，但超时。
商品是数字，重量和对应的价值是相同的，只要装了sum/2重量的时候，背包价值也是sum/2，任务完成。
step2定义：dp[j] 表示： 容量（所能装的重量）为j的背包，所背的物品价值最大可以为dp[j]。
step3递推：dp[j]=max(dp[j],dp[j-num[i]]+nums[i])
step4初始化：因为本题都是正整数，所以全初始化为0就行。如果有负数的,dp[0]=0;
step5遍历：一维所以是先物品后背包，i物品从前往后，j背包从后往前。
class Solution {
public boolean canPartition(int[] nums) {
//覆盖非法情况。
if(nums==null ||nums.length==0) return false;
//先求和，再创建dp数组避免浪费空间。
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];//java会默认将数组的所有元素初始化为 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]);
}
if(dp[target]==target){
return true;
}
}
return dp[target] == target;
}
}
1049.最后一块石头的重量II 最大值问题
首先把题目求最小剩余石头重量转换为求最大的拿走粉碎的石头重量。
然后，每次任取两块，重量越近，可以拿去粉碎的石头重量越大（价值）。任取两块在循环里单次不好实现，那就干脆转换为整体分成两块，每次选择的结果分到两个不同的集合，这样和上一题就很像了。不一样的点在于上一题明确目标值是和的一半，但这题不知道，所以集合可以构建成最大值接近于和的一半。
dpj就是石头重量为j时候，最接近sum/2的重量。
背包容量是什么，小于所有石头的重量和就行。
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])。i是指stones数组里第几块石头，j是指背包里石头重量多少。
遍历条件 先石头i，再背包。
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int stone:stones){
sum+=stone;
}
int target= sum/2;
int[] dp=new int[target+1];
for(int i=0;i<stones.length;i++){
for(int j=target;j>=stones[i];j--){
dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum-2*dp[target];
}
}
494.目标和 组合问题
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
也可以用回溯。
转换问题：假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target，
x = (target + sum) / 2。此时问题就转化为，用nums装满容量为x的背包，有几种方法。
x就是背包容量也就是j，i就是数组中第几个数。
dp[j]就是把容量为j的背包填满有几种方法。
dp[j]=dp[j]+dp[j-nums[i]];
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int num:nums){
sum+=num;
}
int ac_target=(sum-target)/2;
if ((sum - target) % 2 != 0 || sum < Math.abs(target)) {// 边界条件检查
return 0;
}
int[] dp=new int[ac_target+1];
dp[0]=1; // 初始状态：和为 0 的组合数为 1（不选任何数字）
for(int i=0;i<nums.length;i++){
for (int j = ac_target; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[ac_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
特点是两个维度+字符串中判断
dp[i][j]是背包容量中0数为i，1数为j时子集的最大数量。
j背包容量，最大是m+n；
num_0<=m;num_1<=n;
字符串->字符数组后再遍历。
dp[i][j]=max(dp[i][j],dp[i-zero_num][j-one_num]+1) 不取当前子集 以及 取当前子集
dp初始化为0就行，因为这是最大值问题，并且没可能是负数，还可以不装满。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp=new int[m+1][n+1];
int zeronum,onenum;
for(String str:strs){
zeronum=0;
onenum=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];
}
}
2. 完全背包
一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包。
一维完全的遍历顺序都是从小到大。
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
for (int j = weight[i]; j <= W; j++) { // 正序
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); // 最大值
// 或 dp[j] += dp[j - nums[i]]; // 组合数,此时初始化dp[0]=1
}
}
518.零钱兑换II 组合问题
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
class Solution {
public int change(int amount, int[] coins) {
//递推表达式
int[] dp = new int[amount + 1];
//初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
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. 组合总和 Ⅳ 其实是排列
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
和上一题的区别在于 for遍历的顺序以及for从哪开始遍历。
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]+dp[j-nums[i]];
}
}
}
return dp[target];
}
}
322. 零钱兑换 求最小值
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
最值问题，求最小值，初始化最大。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
if (dp[j - coin] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
279.完全平方数 求最小值
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
class Solution {
public int numSquares(int n) {
int[] dp=new int[n+1];//第i的数最少是由几个平分数相加。
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0]=0;
for(int i=1;i*i<=n;i++){
for(int j=i*i;j<=n;j++){
if (dp[j-i*i] != Integer.MAX_VALUE)
dp[j]=Math.min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
}
139.单词拆分 排序问题（是否）+字符串 不简单
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！
dp[j] 表示字符串长度为j时，是否可以拆成一个或多个在字典中出现的单词。
dp[j]=dp[i]&&dp[i-j]
true&&false=false
only true&&true=true
dp[0]=true;
由于字符串组成跟单词顺序有关，所以是排列问题。
所以遍历顺序：先背包后物品。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp=new boolean[s.length()+1];
dp[0]=true;
for(int j=1;j<=s.length();j++){
for(String word:wordDict){
int len=word.length();
//1.背包能装得下当前物品 2.前面装的物品是true 3.当前字符串里的等于遍历的物品
if(j>=len &&dp[j-len] && word.equals(s.substring(j-len,j))){
dp[j]=true;
break;
}
}
}
return dp[s.length()];
}
}
打家劫舍
198.打家劫舍 求最大值
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
最大值问题。不能重复选，01背包。
有条件：如果相邻的前一个偷了，现在就不能拿。
dp[j]表示在到第j间房子能拿到的最大值。
dp[j]=max(dp[j-2]+nums[j],dp[j-1]); 如果要拿就是 前两个的值加上当前房间的钱；不拿就是前一个房间的钱。
初始化：dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);
没有空间限制就是求最大值所以不是背包问题。
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp=new int[nums.length];
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(int j=2;j<nums.length;j++){
dp[j]=Math.max(dp[j-2]+nums[j],dp[j-1]);
}
return dp[nums.length-1];
}
}
213.打家劫舍II 房屋围成圈了 环形结构
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
错误思路：遍历到最后一个房间的时候，max(dp[j-2],dp[j-1])。其余情况,max(dp[j-2]+nums[j],dp[j-1])。这样就相当于永远不偷最后一个房间。
正确思路：必须把问题分成两段：不偷最后一个房间：区间[0, n-2]；不偷第一个房间：区间[1, n-1]。
class Solution {
public int rob(int[] nums) {
if(nums==null||nums.length==0) return 0;
int len=nums.length;
if (len==1) return nums[0];
return Math.max(robAction(nums,0,len-1),robAction(nums,1,len));
}
int robAction(int[] nums,int start,int end){
int dpj1=0,dpj2=0,max=0;
//注意这个顺序
for(int i=start;i<end;i++){
dpj1=max;
max=Math.max(dpj1,dpj2+nums[i]);
dpj2=dpj1;
}
return max;
}
}
//方法2
class Solution {
public int rob(int[] nums) {
int[] dp=new int[nums.length];
int[] dp2=new int[nums.length-1];
if(nums.length==1) return nums[0];
if (nums.length==2) return Math.max(nums[0], nums[1]);
dp[0]=0;
dp[1]=nums[1];
dp2[0]=nums[0];
dp2[1]=Math.max(nums[0],nums[1]);
//不偷第一家
for(int j=2;j<nums.length;j++){
dp[j]=Math.max(dp[j-2]+nums[j],dp[j-1]);
}
//不偷最后一家
for(int j=2;j<nums.length-1;j++){
dp2[j]=Math.max(dp2[j-2]+nums[j],dp2[j-1]);
}
return Math.max(dp[nums.length-1],dp2[nums.length-2]);
}
}
337.打家劫舍 III 结合二叉树
树形dp：数+遍历+dp
多重背包
4. 多重背包问题 I
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan =new Scanner(System.in);
int N=101;
int[] v=new int[N];
int[] w=new int[N];
int[] s=new int[N];
int[] dp=new int[N];
int n=scan.nextInt();
int m=scan.nextInt();
for(int i=1;i<=n;i++){
v[i]=scan.nextInt();
w[i]=scan.nextInt();
s[i]=scan.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
for(int k=1;k<=s[i]&&k*v[i]<=j;k++){
dp[j]=Math.max(dp[j],dp[j-v[i]*k]+k*w[i]);
}
}
}
System.out.println(dp[m]);
}
}
子序列问题
| 问题类型 | 状态定义 | 转移方程 |
|---|---|---|
| 最长递增子序列 | dp[i]：以 nums[i] 结尾 | dp[i] = max(dp[j] + 1)（nums[j] < nums[i]） |
| 最长公共子序列 | dp[i][j]：前 i 和 j 的LCS | dp[i][j] = dp[i-1][j-1] + 1（相等）或 max(dp[i-1][j], dp[i][j-1]) |
| 编辑距离 | dp[i][j]：word1[0…i-1] 到 word2[0…j-1] 的最小操作 | dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 |
| 最长回文子序列 | dp[i][j]：子串 s[i…j] 的最长回文 | dp[i][j] = dp[i+1][j-1] + 2（相等）或 max(dp[i+1][j], dp[i][j-1]) |
300.最长递增子序列 不要求连续
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
dpj表示到第j个数的时候最长的严格递增子序列的长度。
本题最关键的是要想到dp[i]由哪些状态可以推出来，并取最大值，那么很自然就能想到递推公式：dp[i] = max(dp[i], dp[j] + 1);
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp=new int[nums.length];
int res=1;
Arrays.fill(dp,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);
}
}
res=Math.max(dp[i],res);
}
return res;
}
}
674.最长连续递增序列 要求连续
注意递推公式里是 i-1
class Solution {
public int findLengthOfLCIS(int[] nums) {
int[] dp=new int[nums.length];
Arrays.fill(dp,1);
int res=1;
for(int i=0;i<nums.length;i++){
if(i>0){
if(nums[i]>nums[i-1]){
dp[i]=dp[i-1]+1;
}
}
res=res>dp[i] ? res:dp[i];
}
return res;
}
}
718.最长重复子数组 要求连续
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
和前面那题特别像
dp[j]：表示以 nums1[i-1] 和 nums2[j-1] 结尾的 当前公共子数组的长度。
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[] dp=new int[nums2.length+1];
Arrays.fill(dp,0);
int res=0;
for(int i=1;i<=nums1.length;i++){
for(int j=nums2.length;j>0;j--){
if(nums1[i-1]==nums2[j-1])
dp[j]=dp[j-1]+1;
else dp[j]=0;
res=Math.max(res,dp[j]);
}
}
return res;
}
}
1143.最长公共子序列 字符串之间比较 不要求连续
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n1=text1.length();
int n2=text2.length();
int[][] dp=new int[n1+1][n2+1];
int res=0;
for(int i=1;i<=n1;i++){
char char1=text1.charAt(i-1);
for(int j=1;j<=n2;j++){
char char2=text2.charAt(j-1);
if(char1==char2){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
res=Math.max(res,dp[i][j]);
}
}
return res;
}
}
1035.不相交的线 和前一题很像 不要求连续 数组
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
