Java算法之动态规划详解-买卖股票最佳时机 - yiwanbin
source link: https://www.cnblogs.com/ywbmaster/p/17756581.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
①动态规划
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果
⓿动规五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
❶基础规划题
509. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(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
//动态规划
class Solution {
public int fib(int n) {
if (n < 2) 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];
}
}
//优化
class Solution {
public int fib(int n) {
if (n < 2) return n;
int a = 0, b = 1, c = 0;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
//递归
class Solution {
public int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
}
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 阶
本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和
- 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
- 爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶
所以我们得到公式 dp[n] = dp[n−1] + dp[n−2]，同时需要初始化 dp[0]=1 和 dp[1]=1
时间复杂度：O(n)
class Solution {
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. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
- 确定dp数组以及下标的含义
- dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]
- 确定递推公式
- 有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]
- dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
- dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
- 那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？
- 一定是选最小的，所以
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
- dp数组如何初始化
题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说到达第 0 、1个台阶是不花费的，但从 第0 个台阶往上跳的话，需要花费 cost[0]。所以初始化 dp[0] = 0，dp[1] = 0;
- 确定遍历顺序
因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int dp[] = new int[n + 1];
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];
}
}
118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < numRows; i++){
List<Integer> row = new ArrayList<Integer>();
for (int j = 0; j <= i; j++) {
if(j == 0 || j == i) row.add(1);
else row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
}
res.add(row);
}
return res;
}
}
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
我们令 dp[i][j] 是到达 i, j 最多路径
动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1
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++){
//到达i行j列的路径条数
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
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 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] == 0){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
343. 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
动规五部曲，分析如下：
- 确定dp数组以及下标的含义
dp[i]：分拆数字 i，可以得到的最大乘积为dp[i]。
- 确定递推公式
当 i ≥ 2 时，假设对正整数 i 拆分出的第一个正整数是 j（1 ≤ j < i），则有以下两种方案：
- 将
i拆分成j和i−j的和，且i−j不再拆分成多个正整数，此时的乘积是j×(i−j)； - 将
i拆分成j和i−j的和，且i−j继续拆分成多个正整数，此时的乘积是j×dp[i−j]。
递推公式：dp[i]=max{dp[i], j×(i−j), j×dp[i−j]}
- dp的初始化
初始化 dp[2] = 1
- 确定遍历顺序
2 < i <= n1 < j < i
for (int i = 3; i <= n ; i++) {
for (int j = 1; j < i - 1; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
- 举例推导dp数组
class Solution {
public int integerBreak(int n) {
int dp[] = new int[n + 1];
dp[2] = 1;
for(int i = 3; i <= n; i++){
for(int j = 1; j < i; j++){
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}
剑指 Offer 14- II. 剪绳子 II
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
每段长度取3最好
class Solution {
public int cuttingRope(int n) {
if(n == 2)
return 1;
if(n == 3)
return 2;
long res = 1;
while(n > 4){
//每一段取3进行累积
res *= 3;
res = res % 1000000007;
n -= 3;
}
return (int)(res * n % 1000000007);//最后一段不能被3整除，累积上再取mod
}
}
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
- 确定dp数组（dp table）以及下标的含义
dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
- 确定递推公式
假设一共i个节点，对于根节点为j时，左子树的节点个数为j-1，右子树的节点个数为i-j
对于根节点为j时，其递推关系， dp[i] = ∑(1<=j<=i) dp[左子树节点数量] * dp[右子树节点数量]，j是头结点的元素，从1遍历到i为止。
所以递推公式：dp[i] += dp[j - 1] * dp[i - j];
- dp数组如何初始化
- dp[0] = 1;
- dp[1] = 1;
- 确定遍历顺序
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
}
}
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];
}
}
338. 比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
进阶：
- 很容易就能实现时间复杂度为
O(nlogn)的解决方案，你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount）
动态规划法
- 如果这个数是偶数，那么其二进制中
1的个数一定和其1/2的数二进制中1的个数一样，因为1/2就相当于右移1位，即把偶数的最后一个0去掉，不会影响1的个数。res[i] = res[i / 2]
- 如果这个数是奇数：那么其二进制中
1的个数一定是其上一个偶数二进制1的个数+1，因为就相当于将上一个偶数二进制的最后1位的0变成1。res[i] = res[i - 1] + 1—>res[i] = res[i / 2] + 1
- 上述两种情况可以合并成：
res[i]的值等于res[i/2]的值加上i % 2。res[i / 2] + (i % 2)—>res[i >> 1] + (i & 1)
class Solution {
public int[] countBits(int n) {
int[] res = new int[n+1];
res[0] = 0;
for (int i = 1; i <= n; i++) {
if (i % 2 == 1) {
// 奇数：当前奇数的1的个数一定比上一个偶数+1
res[i] = res[i - 1] + 1;
} else {
// 偶数：偶数1的个数一定和其1/2的偶数1的个数一样
res[i] = res[i / 2];
}
}
return res;
}
}
//优化
class Solution {
public int[] countBits(int n) {
int[] res = new int[n + 1];
for (int i = 1; i <= n; i++) {
res[i] = res[i >> 1] + (i & 1);
}
return res;
}
}
1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
class Solution {
int[] dp = new int[38]; //用于防止重复计算
public int tribonacci(int n) {
if(n == 0) return 0;
if(n <= 2) return 1;
int a = 0, b = 1, c = 1;
for(int i = 3; i <= n; i++){
int d = a + b + c;
a = b;
b = c;
c = d;
}
return c;
}
}
❷01背包问题
🌟解题方法
有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
二维数组
- 确定dp数组以及下标的含义
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
- 确定递推公式
有两个方向推出来dp[i][j]
- 不放物品i：由
dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。 - 放物品i：由
dp[i - 1][j - weight[i]]推出，那么dp[i - 1][j - weight[i]] + value[i]，就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- dp数组如何初始化
-
如果背包容量
j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。 -
i0的话，即：
dp[0][j]，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
- 当
j < weight[0]的时候，dp[0][j]应该是0，因为背包容量比编号0的物品重量还小。 - 当
j >= weight[0]时，dp[0][j]应该是value[0]，因为背包容量放足够放编号0物品。
- 当
// dp数组预先初始化就为0，这一步就可以省略，
for (int j = 0 ; j < weight[0]; j++) {
dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
- 确定遍历顺序
先遍历物品还是先遍历背包重量呢？其实都可以！！ 但是先遍历物品更好理解。
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品 从1开始
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
具体实现代码
public class BagProblem {
/**
* 动态规划获得结果
* @param weight 物品的重量
* @param value 物品的价值
* @param bagSize 背包的容量
*/
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
// 创建dp数组
int goods = weight.length; // 获取物品的数量
int[][] dp = new int[goods][bagSize + 1];
// 初始化dp数组
for (int j = weight[0]; j <= bagSize; j++) {
dp[0][j] = value[0];
}
// 填充dp数组
for (int i = 1; i < weight.length; i++) {
for (int j = 1; j <= bagSize; j++) {
if (j < weight[i]) {
/**
* 当前背包的容量都没有当前物品i大的时候，是不放物品i的
* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
*/
dp[i][j] = dp[i-1][j];
} else {
/**
* 当前背包的容量可以放下物品i
* 那么此时分两种情况：
* 1、不放物品i
* 2、放物品i
* 比较这两种情况下，哪种背包中物品的最大价值最大
*/
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
}
}
}
// 打印dp数组
for (int i = 0; i < goods; i++) {
for (int j = 0; j <= bagSize; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println("\n");
}
}
public static void main(String[] args) {
int[] weight = {1,3,4};
int[] value = {15,20,30};
int bagSize = 4;
testWeightBagProblem(weight,value,bagSize);
}
}
- 确定dp数组的定义
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
- 一维dp数组的递推公式
dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] 表示容量为j的背包，放入物品i了之后的价值
此时dp[j]有两个选择
- 一个是取自己
dp[j]相当于二维dp数组中的dp[i-1][j]，即不放物品i， - 一个是取
dp[j - weight[i]] + value[i]，即放物品i
所以递归公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
可以看出相对于二维dp数组的写法，就是把dp[i][j]中i的维度去掉了。
- 一维dp数组如何初始化
dp[0] = 0，因为背包容量为0所背的物品的最大价值就是0。
- 一维dp数组遍历顺序
for(int i = 0; i < weight.size(); i++) { // 遍历物品 从0开始
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！
二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
倒序遍历是为了保证物品i只被放入一次！
具体实现代码
public class BagProblem {
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数组
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWight = 4;
testWeightBagProblem(weight, value, bagWight);
}
}
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
对于这个问题，我们可以先对集合求和，得出 sum，然后把问题转化为背包问题：
给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？
dp 数组的定义：dp[i][j] = x 表示，对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。
根据 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
- 如果不把这第
i个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态dp[i-1][j]，继承之前的结果。 - 如果把这第
i个物品装入了背包，那么是否能够恰好装满背包，取决于状态dp[i-1][j-nums[i]]。
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int num : nums){
sum += num;
}
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
boolean[][] dp = new boolean[n][sum + 1];
for (int i = 0; i < n; i++){
dp[i][0] = true;
}
for(int i = 1; i < n; i++){
for(int j = 1; j <= sum; j++){
if (j - nums[i] < 0) {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[n - 1][sum];
}
}
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
int sum = 0;
for(int num : nums) {
sum += num;
}
//总和为奇数，不能平分
if(sum % 2 != 0) return false;
sum = sum / 2;
int[] dp = new int[sum + 1];
for(int i = 0; i < n; i++) {
for(int j = sum; j >= nums[i]; j--) {
//物品 i 的重量是 nums[i]，其价值也是 nums[i]
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[sum] == sum;
}
}
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
问题转化为：把一堆石头分成两堆，求两堆石头重量差最小值
进一步分析：要让差值小，两堆石头的重量都要接近sum/2
进一步转化：将一堆stone放进最大容量为sum/2的背包，求放进去的石头的最大重量x，最终答案即为sum-2*x
- 确定dp数组以及下标的含义
dp[j]表示容量为j的背包，最多可以背最大重量为dp[j]
- 确定递推公式
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
- dp数组如何初始化
dp[0] = 0
- 确定遍历顺序
如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int i : stones) {
sum += i;
}
int target = sum >> 1;
//初始化dp数组
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. 目标和
给你一个整数数组 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
示例 2：
输入：nums = [1], target = 1
输出：1
回溯
回溯过程中维护一个计数器 count，当遇到一种表达式的结果等于目标数 target 时，将 count 的值加 1。遍历完所有的表达式之后，即可得到结果等于目标数 target 的表达式的数目。
class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
backtrack(nums, target, 0, 0);
return count;
}
public void backtrack(int[] nums, int target, int index, int sum) {
if (index == nums.length) {
if (sum == target) {
count++;
}
} else {
backtrack(nums, target, index + 1, sum + nums[index]);
backtrack(nums, target, index + 1, sum - nums[index]);
}
}
}
记数组的元素和为 sum，添加 - 号的元素之和为 x，则其余添加 + 的元素之和为 sum − x，得到的表达式的结果为(sum − x) − x = target 即 x = sum − target / 2
由于数组 nums 中的元素都是非负整数，x 也必须是非负整数，所以上式成立的前提是 sum−target 是非负偶数。若不符合该条件可直接返回 0。
当 1 ≤ i ≤ n 时，对于数组 nums 中的第 i 个元素 num（i 的计数从 1 开始），遍历 0 ≤ j ≤ x，计算 dp[i][j] 的值：
- 如果
j，则不能选num，此时有dp[i][j]=dp[i−1][j]`； - 如果
j≥num，则如果不选num，方案数是dp[i−1][j]，如果选num，方案数是dp[i−1][j−num]，此时有dp[i][j]=dp[i−1][j]+dp[i−1][j−num]
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, x = diff / 2;
int[][] dp = new int[n][x + 1];
dp[0][0] = 1;
// 第一行要初始化，即物品0，对容量刚好为nums[0]的背包，设置其方式dp[0][nums[0]]为1。
// 有可能第一件物品重量就为0，所以会覆盖dp[0][0],正确应该 +=
for(int j = 0; j < n; j++) {
if(nums[0]==j) dp[0][j]+=1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= x; j++) {
if (j < nums[i]) {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
}
return dp[n - 1][x];
}
}
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, x = diff / 2;
int[] dp = new int[x + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = x; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[x];
}
}
❸完全背包问题
🌟解题方法
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
01背包和完全背包解题步骤唯一不同就是体现在遍历顺序上
首先在回顾一下01背包的核心代码
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]);
}
}
我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：
// 先遍历物品，再遍历背包
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]);
}
}
具体实现代码
//先遍历物品，再遍历背包
private static void testCompletePack(){
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){ // 遍历物品
for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
for (int maxValue : dp){
System.out.println(maxValue + " ");
}
}
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
- 确定dp数组以及下标的含义
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
- 确定递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要再加上一个钱币coins[i]，即dp[j] = dp[j - coins[i]] + 1
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
- dp数组如何初始化
考虑到递推公式的特性，dp[j]必须初始化为一个大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是大值。
凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int max = amount + 1;
//初始化dp数组为最大值
for (int j = 0; j < dp.length; j++) { // Arrays.fill(dp, max);
dp[j] = max;
}
//当金额为0时需要的硬币数目为0
dp[0] = 0;
for(int i = 0; i < coins.length; i++) {
//正序遍历：完全背包每个硬币可以选择多次
for(int j = coins[i]; j <= amount; j++){
if (coins[i] <= j) {
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == max ? -1 : dp[amount];
}
}
518. 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。
示例 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
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
- 确定dp数组以及下标的含义
dp[j]：凑足总额为j的硬币组合数为dp[j]
- 确定递推公式
- 如果不选第
i个硬币：dp[j] - 如果选第
i个硬币：dp[j - coins[i]]
递推公式：dp[j] += dp[j - coins[i]]
- dp数组如何初始化
凑足总金额为0组合数是0，那么dp[0] = 1;
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];
}
}
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
动规五部曲分析如下：
- 确定dp数组（dp table）以及下标的含义
dp[j]：和为j的完全平方数的最少数量
- 确定递推公式
dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j])
- dp数组如何初始化
dp[0]表示和为0的完全平方数的最小数量，那么dp[0]一定是0。
非0下标的dp[j]应该是多少呢？
从递归公式中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。
- 确定遍历顺序
i`必然落在区间 `[1, √n]`。`j`必然落在区间`[i*i, n]
//先遍历物品, 再遍历背包
class Solution {
public int numSquares(int n) {
//dp[j]： 和为j的完全平方数的最少数量
int[] dp = new int[n + 1];
int max = n + 1;
for (int j = 0; j <= n; j++) {
dp[j] = max;
}
dp[0] = 0;
for(int i = 1; i <= Math.sqrt(n); i++){
for(int j = i*i; j <= n; j++){
dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
}
}
return dp[n];
}
}
//先遍历背包, 再遍历物品
class Solution {
public int numSquares(int n) {
int max = n + 1;
int[] dp = new int[n + 1];
// 初始化
Arrays.fill(dp, max);
// 当和为0时，组合的个数为0
dp[0] = 0;
// 遍历背包
for (int j = 1; j <= n; j++) {
// 遍历物品
for (int i = 1; i * i <= j; i++) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
}
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)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
本题要求的是排列，那么这个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 (nums[i] <= j) {
dp[j] += dp[j - nums[i]];
}
}
}
return dp[target];
}
}
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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
dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
Set<String> set = new HashSet(wordDict);
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
// if (set.contains(s.substring(j, i))) dp[i] |= dp[j];
if (dp[j] && set.contains(s.substring(j, i))) {
dp[i] = true;
//break;
}
}
}
return dp[n];
}
}
❹背包问题总结
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])，对应题目如下：
问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]) ，对应题目如下：
01背包
- 二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
- 一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
完全背包
完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
❺股票买卖问题
🌟解题方法
动态规划算法本质上就是穷举「状态」，然后在「选择」中选择最优解。
股票买卖问题，每天都有三种「选择」：买入（ buy）、卖出（sell）、无操作（rest）
但并不是每天都可以任意选择这三种选择的：
-
sell必须在buy之后，buy必须在sell之后。
-
rest应该分两种状态
- 一种是
buy之后的rest（持有了股票）； - 一种是
sell之后的rest（没有持有股票）。
-
而且还有交易次数
k的限制，即buy只能在k > 0的前提下操作。
股票买卖问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：
dp[i][k][0 or 1]
// 0 <= i < n, 1 <= k <= K
// n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
// 此问题共 n × K × 2 种状态，全部穷举就能搞定。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
dp[3][2][1] 的含义：第三天，我现在手上持有着股票，至今已进行 2 次交易。
dp[2][3][0] 的含义：第二天，我现在手上没有持有股票，至今已进行 3 次交易。
我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，已进行 K 次交易，最多获得多少利润。
确定递推公式
状态转移图
今天没有持有股票，有两种可能，我从这两种可能中求最大利润：
- 1、我昨天就没有持有，且截至昨天已进行交易次数为
k；然后我今天选择rest，所以我今天还是没有持有，已进行交易次数为k。代码表示：dp[i-1][k][0] - 2、我昨天持有股票，且截至昨天已进行交易次数为
k-1；但是今天我sell了，所以我今天没有持有股票了，已进行交易次数为k。代码表示：dp[i-1][k-1][1] + prices[i]
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k-1][1] + prices[i])
今天我持有着股票，有两种可能，我从这两种可能中求最大利润：
- 1、我昨天就持有着股票，且截至昨天已进行交易次数为
k；然后今天选择rest，所以我今天还持有着股票，已进行交易次数依然为k。代码表示：dp[i-1][k][1] - 2、我昨天没有持有，且截至昨天已进行交易次数为
k；但今天我选择buy，所以今天我就持有股票了，已进行交易次数为k。代码表示：dp[i-1][k][0] - prices[i]
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
时刻牢记「状态」的定义，状态
k的定义并不是「已进行的交易次数」，而是「最大交易次数的上限限制」。如果确定今天进行一次交易，且要保证截至今天最大交易次数上限为k，那么昨天的最大交易次数上限必须是k - 1。
总结一下：
// 递推公式:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
base case：
dp[-1][...][0] = 0
// 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。
dp[-1][...][1] = -infinity
// 解释：还没开始的时候，是不可能持有股票的。
// 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
dp[...][0][0] = 0
// 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
dp[...][0][1] = -infinity
// 解释：不允许交易的情况下，是不可能持有股票的。
// 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
121. 买卖股票的最佳时机
给定一个数组 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。
方法一：暴力法
- 找出给定数组中两个数字之间的最大差值（即，最大利润）。
- 此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。
即对于每组 i 和 j，其中 j > i ，我们需要找出 max(prices[j]−prices[i])。
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for(int i = 0; i < prices.length - 1; i++){
for(int j = i + 1; j < prices.length; j++){
res = Math.max(res, prices[j] - prices[i]);
}
}
return res;
}
}
- 时间复杂度：O(n^2)。循环运行 n(n−1)/2次。
- 空间复杂度：O(1)。只使用了常数个变量。
方法二：贪心法
我们用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int res = 0;
for (int i = 0; i < prices.length; i++) {
minprice = Math.min(minprice, prices[i]);
res = Math.max(res, prices[i] - minprice);
}
return res;
}
}
- 时间复杂度：O(n)，只需要遍历一次。
- 空间复杂度：O(1)，只使用了常数个变量。
方法三：动态规划优化
套用前文解题方法中递推公式，相当于 k = 1 的情况：
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) = max(dp[i-1][1][1], -prices[i])
// 解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。
//现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。可以进行进一步化简去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
// dp[i][0]代表第i天不持有股票的最大收益
// dp[i][1]代表第i天持有股票的最大收益
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]);
// 由于只能买入和卖出一次，因此如果在第 i 天买入则在买入之前的利润一定是 0，
// 因此在第 i 天买入对应的利润是 −prices[i] 而不是 dp[i−1][0]−prices[i]
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];
}
}
方法四：动态规划优化
- 确定dp数组以及下标的含义
下标为0记录持有股票所得最多现金，下标为1记录不持有股票所得最多现金。
所以本题dp数组就是一个长度为2的数组！
- 确定递推公式
如果第i天持有股票即dp[0]， 那么可以由两个状态推出来
- 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 dp[0],
- 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
- 其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数。
- dp[0] = Math.max(dp[0], -prices[i - 1]);
如果第i天不持有股票即dp[1]， 也可以由两个状态推出来
- 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[1]
- 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[0]
- dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int[2];
// 记录一次交易，一次交易有买入卖出两种状态
// 0代表持有，1代表卖出
dp[0] = -prices[0];
dp[1] = 0;
for (int i = 1; i <= prices.length; i++) {
// 前一天持有；或当天买入
dp[0] = Math.max(dp[0], -prices[i - 1]);
// 前一天卖出；或当天卖出, 当天要卖出，得前一天持有才行
dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);
}
return dp[1];
}
}
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 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
方法一：动态规划
套用前文解题方法中递推公式，相当于 k = ∞ 的情况：
如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的。可以这样改写框架：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
= max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
注意这里和121. 买卖股票的最佳时机唯一不同的地方，就是推导dp[i][1]的时候，第i天买入股票的情况，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][1]一定就是 -prices[i]，而本题，因为一只股票可以买卖多次，所以当第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]);
}
return dp[n - 1][0];
}
}
方法二：贪心法
这道题 「贪心」 的地方在于，只要「今天的股价 > 昨天的股价」就累加差值
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for (int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i - 1]){
res += (prices[i] - prices[i-1]);
}
}
return res;
}
}
309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
套用前文解题方法中递推公式，和上一题类似，区别在于每次 sell 之后要等一天才能继续交易，只要把这个特点融入状态转移方程即可：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
// 解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
由于 i - 2 也可能小于 0，所以再添加一个 i = 1 的 base case
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int n = prices.length;
int[][] dp = new int[n][2];
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
dp[1][1] = Math.max(dp[0][1], dp[0][0] - prices[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]);
}
return dp[n - 1][0];
}
}
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
// base case
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], ((i - 2) < 0 ? 0 : 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
方法一：动态规划
套用前文解题方法中递推公式，相当于 k = ∞ 且含手续费的情况：
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]);
}
return dp[n-1][0];
}
}
方法二：贪心算法
我们开始用buy记录购买时的费用，开始购买时连带交易费一起计算了，之后我们分三种情况进行讨论：
- 这一天的
价格+交易费小于前一天的buy，这时候说明这一天比前一天购买花费更低，将buy更新为这一天的价格+交易费 - 这一天的
价格大于前一天的buy，说明我们是有利润可以获得的，所以我们卖出股票。然后再让buy = 这一天的价格，这相当于一个后悔机制，如果之后我们接着遇到了比这一天卖出价格更高的时候，我们就选择从价格更高的那天卖出。 - 这一天
价格等于前一天的buy(价格+交易费)，这时候我们不做操作
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int buy = prices[0] + fee;
int profit = 0;
for (int i = 1; i < n; ++i) {
if (prices[i] + fee < buy) {
buy = prices[i] + fee;
} else if (prices[i] > buy) {
profit += prices[i] - buy;
buy = prices[i];
}
}
return profit;
}
}
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 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
套用前文解题方法中递推公式，相当于 k = 2 的情况：
class Solution {
public int maxProfit(int[] prices) {
int K = 2;
int n = prices.length;
int[][][] dp = new int[n][K + 1][2];
// base case:
for (int k = 0; k <= K; k++) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
}
// 可省略
// for (int i = 1; i < n; i++) {
// dp[i][0][0] = 0;
// dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][0][0] - prices[i]);
// }
// state transition:
for (int i = 1; i < n; i++) {
for (int k = 1; k <= K; k++) {
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k-1][0] - prices[i]);
}
}
return dp[n - 1][K][0];
}
}
由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：
- 未进行过任何操作；
- 只进行过一次买操作；
- 进行了一次买操作和一次卖操作，即完成了一笔交易；
- 在完成了一笔交易的前提下，进行了第二次买操作；
- 完成了全部两笔交易。
由于第一个状态的利润显然为 000，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大利润记为 buy1，sell1，buy2 以及 sell2。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
//第一次交易的买入和卖出
int buy1 = -prices[0], sell1 = 0;
//第二次交易的买入和卖出
int buy2 = -prices[0], 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;
}
}
188. 买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 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 。
class Solution {
public int maxProfit(int K, int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][K + 1][2];
// base case:
for (int k = 0; k <= K; k++) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
}
// state transition:
for (int i = 1; i < n; i++) {
for (int k = 1; k <= K; k++) {
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k-1][0] - prices[i]);
}
}
return dp[n - 1][K][0];
}
}
相当于 k = K 的情况
class Solution {
public int maxProfit(int K, int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][K + 1][2];
// base case:
for (int k = 0; k <= K; k++) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
}
// state transition:
for (int i = 1; i < n; i++) {
for (int k = 1; k <= K; k++) {
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k-1][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
}
}
return dp[n - 1][K][0];
}
}
相当于 k = 2 的情况
class Solution {
public int maxProfit(int[] prices) {
int K = 2;
int n = prices.length;
int[][][] dp = new int[n][K + 1][2];
// base case:
for (int k = 0; k <= K; k++) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
}
// state transition:
for (int i = 1; i < n; i++) {
for (int k = 1; k <= K; k++) {
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k-1][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
}
}
return dp[n - 1][K][0];
}
}
相当于 k = ∞ 的情况
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
// base case:
dp[0][0] = 0;
dp[0][1] = -prices[0];
// state transition:
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]);
}
return dp[n - 1][0];
}
}
相当于 k = 1 的情况
当然，直接套用代码有点大材小用，只需两个变量记录第i天的最大收益和历史最低股价即可，状态转移：maxProfit=max(maxProfit，prices[i]−minPrice)
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
// state transition:
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];
}
}
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
minprice = Math.min(minprice, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minprice);
}
return maxProfit;
}
}
相当于 k = ∞ 且含冷冻期的情况
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
// state transition:
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], ((i - 2) < 0 ? 0 : dp[i - 2][0]) - prices[i]);
}
return dp[n - 1][0];
}
}
相当于 k = ∞ 且含手续费的情况
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[][] dp = new int [n][2];
// base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
// state transition:
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]);
}
return dp[n-1][0];
}
}
❻打家劫舍问题
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 。
如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 j (j>2) 间房屋，有两个选项：
- 不偷窃第 j 间房屋，偷窃总金额为前 j−1 间房屋的最高总金额。dp[j - 1]
- 偷窃第 j 间房屋，那么就不能偷窃第 j−1 间房屋，偷窃总金额为前 j−2 间房屋的最高总金额与第 j 间房屋的金额之和。 dp[j - 2] + nums[j - 1]
class Solution {
public int rob(int[] nums) {
// dp[j]： j个房屋能够偷窃到的最高金额
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for(int j = 2; j <= nums.length; j++){
dp[j] = Math.max(dp[j - 1], dp[j - 2] + nums[j - 1]);
}
return dp[nums.length];
}
}
上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。
class Solution {
public int rob(int[] nums) {
int length = nums.length;
int first = 0, second = nums[0];
for (int i = 1; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
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 。
示例 3：
输入：nums = [1,2,3]
输出：3
有 n 个房间，编号为 0...n - 1，分成两种情况：
- 偷编号为
0...n - 2的n - 1个房间； 即 偷首元素 - 偷编号为
1...n - 1的n - 1个房间； 即 不偷首元素
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
int[] dp1 = new int[n]; // dp1抢首元素，则不抢尾元素
int[] dp2 = new int[n]; // dp2不抢首元素，则抢尾元素
dp1[0] = nums[0];
dp1[1] = Math.max(nums[1], nums[0]);
dp2[1] = nums[1];
for (int i = 2; i < n; ++i) {
dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
}
return Math.max(dp1[n - 2], dp2[n - 1]);
}
}
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
} else if (length == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
}
public int robRange(int[] nums, int start, int end) {
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
简化一下这个问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。
- dp数组以及下标的含义
下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
所以本题dp数组就是一个长度为2的数组！
讨论当前节点抢还是不抢。如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子
- 偷当前节点：左孩子不偷 + 右孩子不偷 + 当前节点偷
- dp[1] = left[0] + right[0] + root.val;
- 不偷当前节点：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
- dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
- 确定遍历顺序
首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。
通过递归左节点，得到左节点偷与不偷的金钱。
通过递归右节点，得到右节点偷与不偷的金钱。
class Solution {
public int rob(TreeNode root) {
int[] dp = robAction(root);
return Math.max(dp[0], dp[1]);
}
int[] robAction(TreeNode root) {
int dp[] = new int[2];
if (root == null)
return dp;
int[] left = robAction(root.left);
int[] right = robAction(root.right);
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
dp[1] = root.val + left[0] + right[0];
return dp;
}
}
❼子序列/串问题
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
dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。dp[i] 有两种「选择」:
- 要么与前面的相邻子数组连接，形成一个和更大的子数组；
- 要么不与前面的子数组连接，自成一派，自己作为一个子数组。
在这两种选择中择优，就可以计算出最大子数组，而且空间复杂度还可以说使用「滚动变量」优化空间
状态转移方程：dp[i] = max(nums[i], nums[i] + dp[i - 1]);
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for(int i = 1; i < n; i++){
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
int res = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
res = Math.max(res, dp[i]);
}
return res;
}
}
dp[i] 仅仅和 dp[i-1] 的状态有关，那么可以进行进一步优化，将空间复杂度降低：
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int dp_0 = nums[0];
int dp_1 = 0, res = dp_0;
for (int i = 1; i < n; i++) {
dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;
// 顺便计算最大的结果
res = Math.max(res, dp_1);
}
return res;
}
}
升级：返回最大子数组
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
// dp[i] = 以nums[i]结尾的子序列的最大和
int[] dp = new int[nums.length];
dp[0] = nums[0];
int maxStart = 0, maxLen = 1; // 记录最大连续子序列的起点和长度
int start = 0, len = 1; // 记录连续子序列的起点和长度
for(int i = 1; i < nums.length; ++i){
// dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); // 是继续在后面添加，还是另起一个新序列
if(dp[i-1] > 0){
dp[i] = dp[i-1] + nums[i];
len++;
} else {
dp[i] = nums[i];
start = i;
len = 1;
}
if(dp[i] > ans){
maxStart = start;
maxLen = len;
ans = dp[i];
}
}
System.out.println(maxLen);
System.out.println(Arrays.toString(Arrays.copyOfRange(nums, maxStart, maxStart+maxLen)));
return ans;
}
}
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
在 53 题中，子数组 nums[0..i] 的最大元素和是由 nums[0..i-1] 的最大元素和推导出的，但本题变成子数组的乘积则不一定。
比如 nums[i] = -1，nums[0..i-1] 子数组的最大元素乘积为 10，那么我能不能说 nums[0..i] 的最大元素乘积为 max(-1, -1 * 10) = -1 呢？
其实不行，因为可能nums[0..i-1] 子数组的最小元素乘积为 -6，那么 nums[0..i] 的最大元素乘积应该为 max(-1, -1 * 10, -1 * -6) = 6。
所以这道题和 53 题的最大区别在于，要同时维护「以 nums[i] 结尾的最大子数组」和「以 nums[i] 结尾的最小子数组」，以便适配 nums[i] 可能为负的情况。
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
// 定义：以 nums[i] 结尾的子数组，乘积最大为 dp1[i]
int[] dp1 = new int[n];
// 定义：以 nums[i] 结尾的子数组，乘积最小为 dp2[i]
int[] dp2 = new int[n];
dp1[0] = nums[0];
dp2[0] = nums[0];
for(int i = 1; i < n; i++){
dp1[i] = max(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i], nums[i]);
dp2[i] = min(dp1[i - 1] * nums[i], dp2[i - 1] * nums[i], nums[i]);
}
int res = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
res = Math.max(res, dp1[i]);
}
return res;
}
int min(int a, int b, int c) {
return Math.min(Math.min(a, b), c);
}
int max(int a, int b, int c) {
return Math.max(Math.max(a, b), c);
}
}
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
亚信安全2024提前批：最长回文子字符串
求最长回文子字符串 （多组回文长度相同则返回第一组），双指针实现
输入：s = “sjdaiwasdesdsfsdsedsaw1h3u238dsahji1”
输出：”wasdesdsfsdsedsaw”
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
方法一：动态规划
回文天然具有「状态转移」性质：一个长度大于 2 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，不是回文。「动态规划」的方法根据这样的性质得到。
dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。
根据头尾字符是否相等，需要分类讨论：
dp[i][j] = (s[i] == s[j]) and (j - i < 3 || dp[i + 1][j - 1])
- 当只有一个字符时，比如 a 自然是一个回文串。
- 当有两个字符时，首尾相等，则必是一个回文串。
- 当有三个字符时，首尾相等，则必是一个回文串。
- 当有三个以上字符时，去掉首尾再判断剩下串是否是回文
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
// dp[i][j] 表示：子串 s[i..j] 是否为回文子串
boolean[][] dp = new boolean[n][n];
//记录回文长度和起始位置
int maxLen = 1;
int begin = 0;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
//dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 3 || dp[i + 1][j - 1]);
if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
}
//计算最长回文串,只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文
//对比所有的回文串，取出长度最大的，回文串的起始位置
if(dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if(n < 2) {
return s;
}
boolean[][] dp = new boolean[n][n];
char[] charArr = s.toCharArray();
// 初始化：所有长度为 1 的子串都是回文串
for(int i = 0; i < n; i++){
dp[i][i] = true;
}
//记录回文长度和起始位置
int maxLen = 1;
int begin = 0;
// 枚举子串长度
for(int j = 1; j < n; j++){
for(int i = 0; i < j; i++){
if(charArr[i] == charArr[j]){
//首尾相等且长度为2的是回文
if(j - i < 3){
dp[i][j] = true;
} else{
//首尾相等且长度大于2的，去掉首尾再判断
dp[i][j] = dp[i + 1][j - 1];
}
} else{
//首尾不等的串不是回文
dp[i][j] = false;
}
//计算最长回文串,只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文
//对比所有的回文串，取出长度最大的，回文串的起始位置
if(dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
方法二：中心扩散法
找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。
如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数：
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
// 双指针，向两边展开
l--;
r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}
如果输入相同的 l 和 r，就相当于寻找长度为奇数的回文串，
如果输入相邻的 l 和 r，则相当于寻找长度为偶数的回文串。
那么回到最长回文串的问题，解法的大致思路就是：
String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
// 向两边展开
l--;
r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}
}
647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
方法一：动态规划
class Solution {
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for(int j = 0; j < n; j++){
for(int i = 0; i <= j; i++){
if(s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])){
dp[i][j] = true;
count++;
}
}
}
return count;
}
}
方法二：中心扩散法
class Solution {
public int countSubstrings(String s) {
int a = 0;
int b = 0;
for(int i = 0; i < s.length(); i++){
//奇数中心点
a += parlinDrome(s, i, i);
//偶数中心点
b += parlinDrome(s, i, i+1);
}
return a+b;
}
public int parlinDrome(String s, int l, int r){
int count = 0;
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
count++;
}
return count;
}
}
// 中心点有 2 * len - 1 个，分别是 len 个单字符和 len - 1 个双字符。
class Solution {
public int countSubstrings(String s) {
int ans = 0;
for (int center = 0; center < 2 * s.length() - 1; center++) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
ans++;
left--;
right++;
}
}
return ans;
}
}
516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
dp[i][j] 表示 子串 s[i..j] ，最长的回文序列长度是多少。
- 如果 s 的第 i 个字符和第 j 个字符相同的话
dp[i][j] = dp[i + 1][j - 1] + 2
- 如果 s 的第 i 个字符和第 j 个字符不同的话
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
然后注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了。
初始化dp[i][i] = 1 单个字符的最长回文序列是 1 ，结果dp[0][n - 1]
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
// dp 数组全部初始化为 0
int[][] dp = new int[n][n];
// base case
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 反着遍历保证正确的状态转移
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 状态转移方程
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
// 整个 s 的最长回文子串长度
return dp[0][n - 1];
}
}
// 降维dp
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[] dp = new int[n];
for (int i = 0; i < n; i++){
dp[i] = 1;
}
for (int i = n - 1; i >= 0; i--) {
int pre = 0;
for (int j = i + 1; j < n; j++) {
int temp = dp[j];
if (s.charAt(i) == s.charAt(j)){
dp[j] = pre + 2;
}
else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
pre = temp;
}
}
return dp[n - 1];
}
}
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,7,7,7,7,7,7]
输出：1
方法一：动态规划
dp[i] 的值代表以 nums[i] 结尾的最长子序列长度。
设 j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：
- 当 nums[i] > nums[j] 时： nums[i] 可以接在 nums[j]之后，此情况下最长上升子序列长度为
max(dp[j])+1； - 当 nums[i] <= nums[j] 时：nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。
- 初始状态：dp[i]所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。
class Solution {
public int lengthOfLIS(int[] nums) {
// nums[i] 结尾的最长递增子序列的长度
int n = nums.length;
int[] dp = new int[n];
int res = 0;
for(int i = 0; i < n; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
class Solution {
public int lengthOfLIS(int[] nums) {
// dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
int[] dp = new int[nums.length];
// base case：dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; 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);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
}
方法二：贪心+二分
状态设计思想：依然着眼于某个上升子序列的 结尾的元素，如果 已经得到的上升子序列的结尾的数越小，那么遍历的时候后面接上一个数，会有更大的可能构成一个长度更长的上升子序列。既然结尾越小越好，我们可以记录 在长度固定的情况下，结尾最小的那个元素的数值，这样定义以后容易得到「状态转移方程」。
新建数组 tails，用于保存最长上升子序列。tail[i] 表示：长度为 i + 1 的 所有 上升子序列的结尾的最小值。
对原序列进行遍历，将每位元素二分插入 tails 中。
- 如果
tails中元素都比它小，将它插到最后 - 否则，用它覆盖掉比它大的元素中最小的那个。
总之，思想就是让 tails 中存储比较小的元素。这样，tails 未必是真实的最长上升子序列，但长度是对的。
class Solution {
public int lengthOfLIS(int[] nums) {
//tails数组是以当前长度连续子序列的最小末尾元素
//如tail[0]是求长度为1的连续子序列时的最小末尾元素
//例：在 1 6 4中 tail[0]=1 tail[1]=4 没有tail[2] 因为无法到达长度为3的连续子序列
int tails[] = new int[nums.length];
//注意：tails一定是递增的 因为看题解那个动画 我们最开始的那个元素一定找的是该数组里最小的 不然如果不是最小 由于我们需要连续 后面的数一定会更大（这样不好的原因是 数越小 我们找到一个比该数大的数的几率肯定会更大）
int res = 0;
for(int num : nums){
//每个元素开始遍历 看能否插入到之前的tails数组的位置 如果能 是插到哪里
int i = 0, j = res;
while(i < j){
int m = (i + j) / 2;
if(tails[m] < num) i = m + 1;
else j = m;
}
//如果没有到达j==res这个条件 就说明tail数组里只有部分比这个num要小 那么就把num插入到tail数组合适的位置即可 但是由于这样的子序列长度肯定是没有res长的 因此res不需要更新
tails[i] = num;
//j==res 说明目前tail数组的元素都比当前的num要小 因此最长子序列的长度可以增加了
if(j == res) res++;
}
return res;
}
}
72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
dp[i + 1][j + 1] 代表 word1[0..i] 转换成 word2[0..j] 需要最少步数
- 当
word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]； - 当
word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1]+1 表示替换操作，dp[i-1][j]+1 表示删除操作，dp[i][j-1]+1 表示插入操作。
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// base case
for(int i = 1; i <= m; i++){
dp[i][0] = i;
}
for(int j = 1; j <= n; j++){
dp[0][j] = j;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
);
}
}
}
return dp[m][n];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
class Solution {
public int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
// 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
int[][] dp = new int[m + 1][n + 1];
// 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
// base case: dp[0][..] = dp[..][0] = 0
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 现在 i 和 j 从 1 开始，所以要减一
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// s1[i-1] 和 s2[j-1] 必然在 lcs 中
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
}
718. 最长重复子数组
❽用动态规划玩游戏
10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
亚信安全2024提前批-笔试：最长回文子字符串
给定一个字符串和一个匹配模式，实现支持
.和*的正则匹配，其中.匹配任意单个字符，*匹配在它之前的零个或多个字符，被匹配字符串只包含字母，可以为空字符串，匹配模式字符串包含字母和.或*，也客以不带.或*，可以为空字符串
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
状态定义
dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符能否匹配。
状态转移
s 中的字符是固定不变的，我们考虑 p 的第 j 个字符与 s 的匹配情况：
- 1、p[j] 是一个小写字母
a-z，则 s[i] 必须也为同样的小写字母方能完成匹配
- 2、p[j]=
'.'，则 p[j] 一定可以与 s[i] 匹配成功，此时有
-
3、p[j]= ‘*‘，则表示可对 p[j] 的前一个字符 p[j−1] 复制任意次（包括 0 次）。
- 当
s[i]≠p[j-1] && p[j-1] != '.',dp[i][j] = dp[i][j - 2] - 反之
dp[i][j] = dp[i][j - 2] | dp[i - 1][j]
- 当
最终的状态转移方程
初始化
记 s 的长度为 m，p的长度为 n 。为便于状态更新，减少对边界的判断，初始二维 dp 数组维度为 (m+1)×(n+1)，其中第一行和第一列的状态分别表示字符串 s 和 p 为空时的情况。显然，dp[0][0]=True。
对于其他 dp[0][j]，当 p[j]≠'*'时，p[0,…,j] 无法与空字符匹配，因此有 dp[0][j]=False；而当 p[j]='*'时，则有 dp[0][j]=dp[0][j−2]。
⚠️ 需要特别注意的是，由于 dp 数组维度为 (m+1)×(n+1)，在具体代码实现时，s[i−1] 和 p[j−1] 才是分别表示 s 和 p 中的第 i 和第 j 个字符。
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
//初始化
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
//情况1和2
if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
//情况3
} else if (p.charAt(j - 1) == '*') {
if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
dp[i][j] = dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2] | dp[i - 1][j];
}
}
}
}
return dp[m][n];
}
}
44. 通配符匹配
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
对于位置 i，能够装的水为
water[i] = min(
max(height[0..i]), // 左边最高的柱子
max(height[i..end]) // 右边最高的柱子
) - height[i] // 自己柱子高度
 |
 |
|---|---|
// 时间复杂度 O(N^2)，空间复杂度 O(1)
class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
for(int i = 0; i < n; i++){ //柱子i
int l_max = 0, r_max = 0;
//柱子i 右边最大高度
for(int j = i; j < n; j++){
r_max = Math.max(r_max, height[j]);
}
//柱子i 左边最大高度
for(int j = i; j >= 0; j--){
l_max = Math.max(l_max, height[j]);
}
res += Math.min(l_max, r_max) - height[i]; //累加每个柱子水量
}
return res;
}
}
备忘录优化
我们开两个数组 r_max 和 l_max 充当备忘录，l_max[i] 表示位置 i 左边最高的柱子高度，r_max[i] 表示位置 i 右边最高的柱子高度。预先把这两个数组计算好，避免重复计算：
// 时间复杂度 O(N)，空间复杂度 O(N)
class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
// 数组充当备忘录
int[] l_max = new int[n]; //l_max[i] 表示位置 i 左边最高的柱子高度
int[] r_max = new int[n]; //r_max[i] 表示位置 i 右边最高的柱子高度
// 初始化 base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// 从左向右计算 l_max
for (int i = 1; i < n; i++){
l_max[i] = Math.max(height[i], l_max[i - 1]);
}
// 从右向左计算 r_max
for (int i = n - 2; i >= 0; i--){
r_max[i] = Math.max(height[i], r_max[i + 1]);
}
// 计算答案
for (int i = 0; i < n; i++){
res += Math.min(l_max[i], r_max[i]) - height[i];
}
return res;
}
}
用双指针边走边算，节省下空间复杂度。
// 时间复杂度 O(N)，空间复杂度 O(1)
class Solution {
int trap(int[] height) {
int left = 0, right = height.length - 1;
int l_max = 0, r_max = 0;
int res = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]); //l_max 是 height[0..left] 中最高柱子的高度
r_max = Math.max(r_max, height[right]); //r_max 是 height[right..end]最高柱子的高度
// res += min(l_max, r_max) - height[i]
if (l_max < r_max) {
res += l_max - height[left];
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
}
}
l_max 和 r_max 代表的是 height[0..left] 和 height[right..end] 的最高柱子高度。比如这段代码：
if (l_max < r_max) {
res += l_max - height[left];
left++;
}
此时的 l_max 是 left 指针左边的最高柱子，但是 r_max 并不一定是 left 指针右边最高的柱子
 |
 |
|---|---|
我们只在乎 min(l_max, r_max)。对于上图的情况，我们已经知道 l_max < r_max 了，至于这个 r_max 是不是右边最大的，不重要。重要的是 height[i] 能够装的水只和较低的 l_max 之差有关
64. 最小路径和
给定一个包含非负整数的 m*n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
示例 1：
img
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
//时间复杂度：O(mn)，空间复杂度：O(mn)
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// dp[i][j] 代表走到 (i,j) 的最小路径和。
int[][] dp = new int[m][n];
// 初始化
dp[0][0] = grid[0][0];
for(int i = 1; i < m; i++){
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int j = 1; j < n; j++){
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
//优化 时间复杂度：O(mn)，空间复杂度：O(1)
//其实我们完全不需要建立 dp 矩阵浪费额外空间，直接遍历 grid[i][j] 修改即可。这是因为：grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] ；原 grid 矩阵元素中被覆盖为 dp 元素后（都处于当前遍历点的左上方），不会再被使用到。
class Solution {
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i == 0 && j == 0) continue;
else if(i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];
else if(j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];
else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
}
return grid[n - 1][m - 1];
}
}
221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
输入：matrix = [["0"]]
输出：0
当 matrix[i][j] 为 1，且它的左边、上边、左上边都存在正方形时，matrix[i][j] 才能够作为一个更大的正方形的右下角
所以我们可以定义这样一个二维 dp 数组：以 matrix[i][j] 为右下角元素的最大的全为 1 正方形矩阵的边长为 dp[i][j]。
有了这个定义，状态转移方程就是：
if (matrix[i][j] == 1)
// 类似「水桶效应」，最大边长取决于边长最短的那个正方形
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1;
else
dp[i][j] = 0;
题目最终想要的答案就是最大边长 max(dp[..][..]) 的平方。
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
//定义：以 matrix[i][j] 为右下角元素的全为 1 正方形矩阵的最大边长为 dp[i][j]。
int[][] dp = new int[m][n];
// base case，第一行和第一列的正方形边长
for(int i = 0; i < m; i++){
dp[i][0] = matrix[i][0] - '0';
}
for(int i = 0; i < n; i++){
dp[0][i] = matrix[0][i] - '0';
}
// 进行状态转移
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == '0') {
// 值为 0 不可能是正方形的右下角
continue;
}
dp[i][j] = Math.min(Math.min(
dp[i - 1][j],
dp[i][j - 1]),
dp[i - 1][j - 1]
) + 1;
}
}
int len = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
len = Math.max(len, dp[i][j]);
}
}
return len * len;
}
}
790. 多米诺和托米诺平铺
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1
输出: 1
定义 f[i] 表示平铺 2×i 面板的方案数，那么答案为 f[n]。
尝试计算 f 的前几项，并从中找到规律，得到 f[n] 的递推式：
class Solution {
static final long MOD = (long) 1e9 + 7;
public int numTilings(int n) {
if (n == 1) return 1;
// dp[n] 平铺 2 x n 面板方法的数量
long[] dp = new long[n + 1];
dp[0] = dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i)
dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % MOD;
return (int)dp[n];
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK