1. 斐波那契数列

    /*** 要点1：*      从已知子问题的解，推导出当前问题的解*      推倒过程中可以表达为一个数学公式* 要点2：*      用一维或二维数组来保存之前的计算结果（可以进一步优化）** Dynamic-Programming - 由Bellman提出* 动态     编程*  programming - 在这里指用数学方法来根据子问题求解当前问题（通俗易懂就是找到递推公式）*  Dynamic     - 指缓存上一步结果，根据上一步结果计算当前结果（多阶段进行）**  合在一起：*      将找出递推公式，将当前问题分解成子问题，分阶段进行求解*      求解过程中缓存子问题的解，避免重复计算* @param n* @return*/public static int fibonacci(int n) {int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;if(n < 2) {return dp[n];}for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}

降维

    public static int fibonacci(int n) {if(n == 0) {return 0;}if(n == 1) {return 1;}int a = 0, b = 1;for(int i = 2; i <= n; i++) {int c = a + b;a = b;b = c;}return b;}

2. 最短路径 - Bellman-Ford

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;public class BellmanFord {static class Edge {int from;int to;int weight;public Edge(int from, int to, int weight) {this.from = from;this.to = to;this.weight = weight;}}/*f(v) 用来表示从起点出发，到达 v 这个顶点的最短距离初始时f(v) = 0   当 v==起点 时f(v) = ∞   当 v!=起点 时之后新           旧     所有fromf(to) = min(f(to), f(from) + from.weight)from 从哪来to   到哪去f(v4) = min( ∞, f(v3) + 11 ) = 20f(v4) = min( 20, f(v2) + 15 ) = 20v1  v2  v3  v4  v5  v60   ∞   ∞   ∞   ∞   ∞0   7   9   ∞   ∞   14  第一轮0   7   9   20  23  11  第二轮0   7   9   20  20  11  第三轮0   7   9   20  20  11  第四轮0   7   9   20  20  11  第五轮*/public static void main(String[] args) {List<Edge> edges = List.of(new Edge(6, 5, 9),new Edge(4, 5, 6),new Edge(1, 6, 14),new Edge(3, 6, 2),new Edge(3, 4, 11),new Edge(2, 4, 15),new Edge(1, 3, 9),new Edge(1, 2, 7));int[] dp = new int[7];  // 一维数组用来缓存结果dp[1] = 0;  // 起点for (int i = 2; i < dp.length; i++) {dp[i] = Integer.MAX_VALUE;}print(dp);for (int i = 0; i < 5; i++) {  // edges.length - 2for (Edge edge : edges) {if(dp[edge.from] != Integer.MAX_VALUE) {dp[edge.to] = Integer.min(dp[edge.to], dp[edge.from] + edge.weight);}}}print(dp);}static void print(int[] dp) {System.out.println(Arrays.stream(dp).mapToObj(i -> i == Integer.MAX_VALUE ? "∞" : String.valueOf(i)).collect(Collectors.joining(",", "[", "]")));}
}

3. 不同路径

一个机器人位于一个 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

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 10^9

解法一：动态规划

class Solution {public int uniquePaths(int m, int n) {int dp[][] = new int[m][n];for (int i = 0; i < m; i++) {// 初始化第一列为0dp[i][0] = 1;}for (int i = 0; i < n; i++) {// 初始化第一行为0dp[0][i] = 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 {public int uniquePaths(int m, int n) {int[] dp = new int[n];Arrays.fill(dp, 1);for (int i = 1; i < m; i++) {dp[0] = 1;for (int j = 1; j < n; j++) {dp[j] = dp[j] + dp[j - 1];}}return dp[n - 1];}
}

4. 0-1背包问题

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;
import java.util.stream.IntStream;public class KnapsackProblem {/*1. n个物品都是固体，有重量和价值2. 现在你要取走不超过 10克 的物品3. 每次可以不拿或全拿，问最高价值是多少编号 重量(g)  价值(元)                        简称1   4       1600           黄金一块   400    A2   8       2400           红宝石一粒 300    R3   5       30             白银一块         S0   1       1_000_000      钻石一粒          D1_001_6301_002_400*//*0   1   2   3   4   5   6   7   8   9   100   0   0   0   0   A   A   A   A   A   A   A       黄金1   0   0   0   0   A   A   A   A   R   R   R       红宝石2   0   0   0   0   A   A   A   A   R   R   R       白银3   0   D   D   D   D   DA  DA  DA  DA  DR  DR      钻石if(装不下) {dp[i][j] = dp[i-1][j]} else { 装得下dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight])}*/static class Item {int index;String name;int weight;int value;public Item(int index, String name, int weight, int value) {this.index = index;this.name = name;this.weight = weight;this.value = value;}@Overridepublic String toString() {return "Item(" + name + ")";}}public static void main(String[] args) {Item[] items = new Item[]{new Item(1, "黄金", 4, 1600),new Item(2, "宝石", 8, 2400),new Item(3, "白银", 5, 30),new Item(4, "钻石", 1, 10_000),};System.out.println(select(items, 10));}/*** 最高价值* @param items 物品* @param total 容量* @return*/private static int select(Item[] items, int total) {// 行代表装入的物品，列代表背包的容量int[][] dp = new int[items.length][total + 1];print(dp);Item item0 = items[0];for (int j = 0; j < total + 1; j++) {if(j >= item0.weight) {// 处理第一行dp[0][j] = item0.value;}}print(dp);for (int i = 1; i < dp.length; i++) {Item item = items[i];for (int j = 1; j < total + 1; j++) {// x为上一次同容量背包的最大价值int x = dp[i - 1][j];if(j >= item.weight) {// j - item.weight：当前背包容量 - 这次物品重量 = 剩余背包容量// y：剩余背包空间能装下的最大价值 + 这次物品价值int y = dp[i - 1][j - item.weight] + item.value;dp[i][j] = Integer.max(x, y);} else {dp[i][j] = x;}}print(dp);}return dp[dp.length - 1][total];}static void print(int[][] dp) {System.out.println("   " + "-".repeat(63));Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();System.out.printf(("%5d ".repeat(dp[0].length)) + "%n", array);for (int[] d : dp) {array = Arrays.stream(d).boxed().toArray();System.out.printf(("%5d ".repeat(d.length)) + "%n", array);}}
}

降维

    private static int select(Item[] items, int total) {int[] dp = new int[total + 1];for (Item item : items) {for(int j = total; j > 0; j--) {if(j >= item.weight) {  // 装得下dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);}}System.out.println(Arrays.toString(dp));}return dp[total];}

5. 完全背包问题

每件物品的数量可以有无限多

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;
import java.util.stream.IntStream;/*** 完全背包问题 - 动态规划* 每件物品有无限多*/
public class KnapsackProblemComplete {static class Item {int index;String name;int weight;int value;public Item(int index, String name, int weight, int value) {this.index = index;this.name = name;this.weight = weight;this.value = value;}@Overridepublic String toString() {return "Item(" + name + ")";}}public static void main(String[] args) {Item[] items = new Item[]{new Item(1, "青铜", 2, 3),    // cnew Item(2, "白银", 3, 4),    // snew Item(3, "黄金", 4, 7),    // a};System.out.println(select(items, 6));}/*0   1   2   3   4   5   6放入第一件物品    1   0   0   c   c   cc  cc  ccc     青铜 重2放入第二件物品    2   0   0   c   s   cc  sc  ccc     白银 重3放入第三件物品    3   0   0   c   s   a   a   ac      黄金 重4if(放得下) {dp[i][j] = max(dp[i-1][j], dp[i][j-item.weight] + item.value)} else {// 沿用上一次的最大价值dp[i][j] = dp[i-1][j]}*/private static int select(Item[] items, int total) {int[][] dp = new int[items.length][total + 1];Item item0 = items[0];// 先初始化第一行for (int j = 0; j < total + 1; j++) {if(j >= item0.weight) {dp[0][j] = dp[0][j - item0.weight] + item0.value;}}print(dp);// 处理剩下的行for (int i = 1; i < items.length; i++) {for (int j = 0; j < total + 1; j++) {Item item = items[i];int x = dp[i - i][j];  // 上次的最大价值if(j >= item.weight) {dp[i][j] = Integer.max(x, dp[i][j - item.weight] + item.value);} else {dp[i][j] = x;}}print(dp);}return dp[items.length - 1][total];}static void print(int[][] dp) {System.out.println("   " + "-".repeat(63));Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();System.out.printf(("%5d ".repeat(dp[0].length)) + "%n", array);for (int[] d : dp) {array = Arrays.stream(d).boxed().toArray();System.out.printf(("%5d ".repeat(d.length)) + "%n", array);}}
}

降维

    private static int select2(Item[] items, int total) {int[] dp = new int[total + 1];for (Item item : items) {for (int j = 0; j < total + 1; j++) {if (j >= item.weight) {// 放得下                      剩余空间能装的最大价值     当前物品的价值dp[j] = Integer.max(dp[j], dp[j - item.weight] + item.value);}}System.out.println(Arrays.toString(dp));}return dp[total];}

完全背包 与 0-1背包的区别

6. 零钱兑换问题

. - 力扣（LeetCode）

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;
import java.util.stream.IntStream;/*** 零钱兑换 - 动态规划* 凑成总金额的凑法中，需要硬币数最少个数是几？*/
public class ChangeMakingProblem {/*面值    0        1        2        3        4        51    0        1        11       111      1111     111112    0        1        2        21       22       2215    0        1        2        21       22       5面值    0        1        2        3        4        510    0        max      max      max      max      max总金额❤  - 类比为背包容量硬币面值  - 类比为物品重量硬币个数  - 类比为物品价值，固定为1 （求价值(个数)最小的）if(装得下) {min(上次价值(个数), 剩余容量能装下的最小价值(个数)+1)dp[i][j] = min(dp[i-1][j], dp[i][j-item.weight] + 1)} else {保留上次价值(个数)不变dp[i][j] = dp[i-1][j]}*/public int coinChange(int[] coins, int amount) {int[][] dp = new int[coins.length][amount + 1];int max = amount + 1;for (int j = 1; j < amount + 1; j++) {if (j >= coins[0]) {  // 装得下dp[0][j] = dp[0][j - coins[0]] + 1;} else {dp[0][j] = max;  // 初始化为amount + 1 -> 凑成amount的硬币个数不会大于amount}}print(dp);for (int i = 1; i < coins.length; i++) {for (int j = 1; j < amount + 1; j++) {if (j >= coins[i]) {dp[i][j] = Integer.min(dp[i - 1][j], dp[i][j - coins[i]] + 1);} else {dp[i][j] = dp[i - 1][j];}}print(dp);}return dp[coins.length - 1][amount] > amount ? -1 : dp[coins.length - 1][amount];}public static void main(String[] args) {ChangeMakingProblem change = new ChangeMakingProblem();// int count = change.coinChange(new int[]{1, 2, 5}, 5);int count = change.coinChange(new int[]{25, 10, 5, 1}, 41);System.out.println(count);}static void print(int[][] dp) {System.out.println("-".repeat(18));Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);for (int[] d : dp) {array = Arrays.stream(d).boxed().toArray();System.out.printf(("%2d ".repeat(d.length)) + "%n", array);}}
}

降维

    public int coinChange2(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int coin : coins) {for (int j = coin; j < amount + 1; j++) {dp[j] = Math.min(dp[j], 1 + dp[j - coin]);}}return dp[amount] > amount ? -1 : dp[amount];}

零钱兑换Ⅱ

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;
import java.util.stream.IntStream;/*** 零钱兑换 - 动态规划* 凑成总金额的凑法中，需要硬币数最少个数是几？*/
public class ChangeMakingProblem {/*面值    0        1        2        3        4        51    0        1        11       111      1111     111112    0        1        2        21       22       2215    0        1        2        21       22       5面值    0        1        2        3        4        510    0        max      max      max      max      max总金额❤  - 类比为背包容量硬币面值  - 类比为物品重量硬币个数  - 类比为物品价值，固定为1 （求价值(个数)最小的）if(装得下) {min(上次价值(个数), 剩余容量能装下的最小价值(个数)+1)dp[i][j] = min(dp[i-1][j], dp[i][j-item.weight] + 1)} else {保留上次价值(个数)不变dp[i][j] = dp[i-1][j]}*//*public int coinChange(int[] coins, int amount) {int[][] dp = new int[coins.length][amount + 1];int max = amount + 1;for (int j = 1; j < amount + 1; j++) {if (j >= coins[0]) {  // 装得下dp[0][j] = dp[0][j - coins[0]] + 1;} else {dp[0][j] = max;  // 初始化为amount + 1 -> 凑成amount的硬币个数不会大于amount}}print(dp);for (int i = 1; i < coins.length; i++) {for (int j = 1; j < amount + 1; j++) {if (j >= coins[i]) {dp[i][j] = Integer.min(dp[i - 1][j], dp[i][j - coins[i]] + 1);} else {dp[i][j] = dp[i - 1][j];}}print(dp);}return dp[coins.length - 1][amount] > amount ? -1 : dp[coins.length - 1][amount];}public static void main(String[] args) {ChangeMakingProblem change = new ChangeMakingProblem();// int count = change.coinChange(new int[]{1, 2, 5}, 5);int count = change.coinChange(new int[]{25, 10, 5, 1}, 41);System.out.println(count);}static void print(int[][] dp) {System.out.println("-".repeat(18));Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);for (int[] d : dp) {array = Arrays.stream(d).boxed().toArray();System.out.printf(("%2d ".repeat(d.length)) + "%n", array);}}public int coinChange2(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int coin : coins) {for (int j = coin; j < amount + 1; j++) {dp[j] = Math.min(dp[j], 1 + dp[j - coin]);}}return dp[amount] > amount ? -1 : dp[amount];}*//*面值    0      1      2      3      4      5         总金额-背包容量1      1      1      11     111    1111   111112      1      1      11     111    1111   111112      21     211    211122     2215      1      1      11     111    1111   111112      21     211    211122     2215if(放得下)dp[i][j] = dp[i-1][j] + dp[i][j-coin]else(放不下)dp[i][j] = dp[i-1][j]*/public int change(int amount, int[] coins) {int[][] dp = new int[coins.length][amount + 1];for (int i = 0; i < coins.length; i++) {// 初始化第0列 为1dp[i][0] = 1;}for (int j = 1; j < amount + 1; j++) {// 初始化第一行if(j >= coins[0]) {dp[0][j] = dp[0][j - coins[0]];}}print(dp);for (int i = 1; i < coins.length; i++) {for (int j = 1; j < amount + 1; j++) {if(j >= coins[i]) {dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];} else {dp[i][j] = dp[i - 1][j];}}print(dp);}return dp[coins.length - 1][amount];}public static void main(String[] args) {ChangeMakingProblem change = new ChangeMakingProblem();int count = change.change( 41, new int[]{25, 10, 5, 1});System.out.println(count);}static void print(int[][] dp) {System.out.println("-".repeat(18));Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);for (int[] d : dp) {array = Arrays.stream(d).boxed().toArray();System.out.printf(("%2d ".repeat(d.length)) + "%n", array);}}
}

降维：

    public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for (int coin : coins) {for (int j = coin; j < amount + 1; j++) {dp[j] = dp[j] + dp[j - coin];}}return dp[amount];}

7. 钢条切割问题

你有一条长度为 n 的钢条，并且有一个数组 values，其中 values[i] 表示长度为 i 的钢条的价格。你的目标是通过合适的切割使得从钢条中获得的总价值最大。

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;
import java.util.stream.IntStream;/*** 钢条切割问题 - 动态规划* 给你一条钢条，怎么切使其价值最大*/
public class CutRodProblem {/*长度  0   1   2   3   4   5   6   7   8   9   10价值  0   1   5   8   9   10  17  17  20  24  30if(放得下)dp[i][j]=max(dp[i-1][j],当前物品价值+dp[i][j-物品重量]else(放不下)dp[i][j]=dp[i-1][j]注：()里的是价值钢铁总长度    0   1   2   3   4       钢条总长度=背包容量切分长度  1       1   11  111 1111(1) (2) (3) (4)2       1   11  111 11112   21  21122(1) (5) (6) (10)3       1   11  111 11112   21  2113   2231(1) (5) (8) (10)4       1   11  111 11112   21  2113   22314(1) (5) (8) (10)物品重量*/static int cut(int[] values, int n) {int[][] dp = new int[values.length][n + 1];for (int i = 1; i < values.length; i++) {for (int j = 1; j < n + 1; j++) {if(j >= i) {// 放得下dp[i][j] = Integer.max(dp[i - 1][j], values[i] + dp[i][j - i]);} else {// 放不下dp[i][j] = dp[i - 1][j];}}print(dp);}return dp[values.length - 1][n];}public static void main(String[] args) {System.out.println(cut(new int[]{0, 1, 5, 8, 9}, 4));}static void print(int[][] dp) {System.out.println("-".repeat(18));Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);for (int[] d : dp) {array = Arrays.stream(d).boxed().toArray();System.out.printf(("%2d ".repeat(d.length)) + "%n", array);}}
}

降维

    static int cut(int[] values, int n) {int[] dp = new int[n + 1];for (int i = 1; i < values.length; i++) {for (int j = i; j < n + 1; j++) {dp[j] = Integer.max(dp[j], values[i] + dp[j - i]);}System.out.println(Arrays.toString(dp));}return dp[n];}

7.1 整数拆分

给定一个正整数 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。

提示:

• 2 <= n <= 58

解法一：动态规划

class Solution {public int integerBreak(int n) {int[][] dp = new int[n][n + 1];// 初始化第一行和第一列Arrays.fill(dp[0], 1);for (int i = 0; i < n; i++) {dp[i][0] = 1;}for (int i = 1; i < n; i++) {for (int j = 0; j < n + 1; j++) {if (j >= i) {dp[i][j] = Integer.max(dp[i - 1][j], i * dp[i][j - i]);} else {dp[i][j] = dp[i - 1][j];}}}return dp[n - 1][n];}
}

降维：

    public int integerBreak(int n) {int[] dp = new int[n + 1];// 初始化第一行和第一列dp[0] = 1;for (int i = 1; i < n; i++) {for (int j = 0; j < n + 1; j++) {if(j >= i) {dp[j] = Integer.max(dp[j] , i * dp[j - i]);}}}return dp[n];}

优化思路：

1. 动态规划数组定义：定义一个数组dp，其中dp[i]表示整数i的最大乘积

2. 初始化：dp[0]和dp[1]可以设为0，因为它们没有有效的拆分

3. 状态转移方程：对于每个数i从2到n，遍历所有可能的拆分点j（1到i.2），更新dp[i]。拆分出一部分可以是j，另一部分是i - j，所有计算乘积时需要考虑两种情况：

• 直接使用拆分后的部分：j * (i - j)
• 继续拆分：j * dp[i - j]（将其继续拆分以获得更大的乘积）
• dp[i]=max(dp[i],j×max(i−j,dp[i−j]))

class Solution {public static int integerBreak(int n) {// dp数组初始化int[] dp = new int[n + 1];// 遍历每个数for (int i = 2; i <= n; i++) {for (int j = 1; j <= i / 2; j++) {// Max of the product with and without breaking furtherdp[i] = Math.max(dp[i], j * Math.max(i - j, dp[i - j]));}}return dp[n];}}

8. 最长公共子串

给定两个字符串 a 和 b，请你找出这两个字符串之间的最长公共子串的长度。

输入：

• 字符串 a：一个非空字符串。
• 字符串 b：一个非空字符串。

输出：

• 一个整数，表示字符串 a 和字符串 b 之间的最长公共子串的长度。

示例：

输入： a = "abcde" b = "abfce"

输出： 最长公共子串的长度为 2（公共子串为 "ab"）

备注：

• 如果没有公共子串，返回 0。
• 字符串中可包含大小写字母、数字和符号。

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;public class LCSubstring {static void print(int[][] dp, String a, String b) {System.out.println("-".repeat(23));Object[] array = a.chars().mapToObj(i -> String.valueOf((char) i)).toArray();System.out.printf("  "+"%2s ".repeat(a.length()) + "%n", array);for (int i = 0; i < b.length(); i++) {int[] d = dp[i];array = Arrays.stream(d).boxed().toArray();System.out.printf(b.charAt(i) + " " + "%2d ".repeat(d.length) + "%n", array);}}public static void main(String[] args) {System.out.println(lcs("itheima", "thema"));}/*前一行的前一列的值加1（对角线）i   t   h   e   i   m   at  0   1   0   0   0   0   0h  0   0   2   0   0   0   0e  0   0   0   3   0   0   0m  0   0   0   0   0   1   0a  0   0   0   0   0   0   2if(相同字符) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = 0;}*/private static int lcs(String a, String b) {int[][] dp = new int[a.length()][b.length()];int max = 0;for (int i = 0; i < a.length(); i++) {for (int j = 0; j < b.length(); j++) {if(a.charAt(j) == b.charAt(i)) {if(i == 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j - 1] + 1;}max = Integer.max(dp[i][j], max);} else {dp[i][j] = 0;}}}// return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().orElseThrow();return max;}
}

8.1 最长重复子数组

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

解法一：动态规划

class Solution {/*前一行的前一列的值加1（对角线）1   2   3   2   13  0   0   1   0   02  0   1   0   2   01  1   0   0   0   34  0   0   0   0   07  0   0   0   0   0if(相同字符) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = 0;}*/public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length][nums2.length];int max = 0;for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {if (nums1[i] == nums2[j]) {if (i == 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j - 1] + 1;}max = Integer.max(max, dp[i][j]);} else {dp[i][j] = 0;}}}return max;}
}

解法二：降维

class Solution {/*前一列的值加1（对角线）3   2   1   4   71  0   0   1   0   02  0   1   0   0   03  1   0   0   0   32  0   2   0   0   01  0   0   3   0   0if(相同字符) {dp[j] = dp[j - 1] + 1;} else {dp[j] = 0;}*/public int findLength(int[] nums1, int[] nums2) {int[] dp = new int[nums2.length];int max = 0;for (int i = 0; i < nums1.length; i++) {for (int j = nums2.length - 1; j >= 0; j--) {if(nums1[i] == nums2[j]) {if(i == 0 || j == 0) {dp[j] = 1;} else {dp[j] = dp[j - 1] + 1;}max = Integer.max(max, dp[j]);} else {dp[j] = 0;}}}return max;}
}

解法三：

class Solution {/*前一列的值加1（对角线）3   2   1   4   71  0   0   0   1   02  0   0   1   0   03  0   1   0   0   32  0   0   2   0   01  0   0   0   3   0if(相同字符) {dp[j] = dp[j - 1] + 1;} else {dp[j] = 0;}*/public int findLength(int[] nums1, int[] nums2) {int m = nums1.length + 1;int n = nums2.length + 1;int[] dp = new int[n];int max = 0;for (int i = 1; i < m; i++) {for (int j = n - 1; j > 0; j--) {if (nums1[i - 1] == nums2[j - 1]) {dp[j] = dp[j - 1] + 1;max = Integer.max(max, dp[j]);} else {dp[j] = 0;}}}return max;}
}

9. 最长公共子序列

9.1 最长公共子序列

给定两个字符串 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 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

解法一：动态规划

class Solution {/*a  b  c  x  y  z0  0  0  0  0  0  0a  0  1  1  1  1  1  1b  0  1  2  2  2  2  2x  0  1  2  2  3  3  3y  0  1  2  2  3  4  4z  0  1  2  2  3  4  5相同字符找到上一行上一列数值+1不同字符max(上一行, 上一列)*/public int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i < m + 1; i++) {char a = text1.charAt(i - 1);for (int j = 1; j < n + 1; j++) {char b = text2.charAt(j - 1);if(a == b) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}
}

9.2 两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例  2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

• 1 <= word1.length, word2.length <= 500
• word1 和 word2 只包含小写英文字母

解法一：动态规划。minDistance = 字符串1的长度 + 字符串2的长度 -  2 * 两个字符串的最长公共子序列。执行耗时5ms

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i < m + 1; i++) {char a = word1.charAt(i - 1);for (int j = 1; j < n + 1; j++) {char b = word2.charAt(j - 1);if(a == b) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);}}}return m + n - 2 * dp[m][n];}public static void main(String[] args) {Solution solution = new Solution();// minDistance = 字符串1的长度 + 字符串2的长度 -  2 * 两个字符串的最长公共子序列System.out.println(solution.minDistance("leetcode", "etco"));  // 8-4 + 4-4 = 4System.out.println(solution.minDistance("eat", "sea"));  // 3-2 + 3-2 = 2System.out.println(solution.minDistance("park", "spake"));  // 4-3 + 5-3}
}

优化：执行耗时4ms

class Solution {public int minDistance(String text1, String text2) {int m = text1.length();int n = text2.length();char[] chars1 = text1.toCharArray();char[] chars2 = text2.toCharArray();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i < m + 1; i++) {char x = chars1[i - 1];for (int j = 1; j < n + 1; j++) {char y = chars2[j - 1];if (x == y) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);}}}return m + n - 2 * dp[m][n];}
}

10. 最长递增子序列

给你一个整数数组 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

提示：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

解法一：动态规划。执行耗时82ms

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];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] = Integer.max(dp[i], dp[j] + 1);}}}return Arrays.stream(dp).max().getAsInt();}
}

优化：执行耗时58ms

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];int max = 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] = Integer.max(dp[i], dp[j] + 1);}}max = Integer.max(max, dp[i]);}return max;}
}

解法二：二分查找 + 动态规划。执行耗时2ms

算法思路：维护一个辅助数组，通过二分查找来快速定位和更新这个数组

1. 定义一个辅助数组tails，其中tails[i]表示当前找到的长度为i + 1的递增子序列的最小尾值

2. 遍历输入的数组nums。对于每一个元素：

• 使用二分查找法确定该元素在tails数组中的位置
• 如果该元素可以扩展tails，则将其追加到tails末尾
• 如果它可以替换tails数组中的某个值（即找到合适位置），则进行替换，保持tails的最小尾值

3. 最终，tails数组的长度即为最长递增子序列的长度

class Solution {public int lengthOfLIS(int[] nums) {if (nums.length == 0) {return 0;}int[] tails = new int[nums.length];int size = 0; // 维护tails数组的实际长度for (int num : nums) {int left = 0, right = size;// 二分查找尾值的位置while (left < right) {int mid = (left + right) >>> 1;if (tails[mid] < num) {// 在右边left = mid + 1;} else {// 在左边right = mid;}}// 如果找到了可以替换的位置，进行替换tails[left] = num;// 更新tails数组的长度if (left == size) {size++;}}return size;}
}

11. Catalan数

Catalan数是一类在组合数学中广泛出现的自然数序列。其第n个Catalan数通常用Cn表示，可以通过以下公式计算：

Catalan数的性质和应用

Catalan数有许多重要的性质和应用，以下是一些常见的规律和应用场景：

1. 递归关系：

这个递归关系表示，第n个Catalan数可以由之前的数的组合得出。

2. 初始值：

• C0​=1
• C1=1C1​=1
• C2=2C2​=2
• C3=5C3​=5
• C4=14C4​=14
• C5=42C5​=42

3. 图形解析：

Catalan数在许多类型的组合结构中出现，常见的有：

• 合法的括号组合：例如，给定n个括号，存在Cn中合法的括号组合方式
• 二叉树：有n个节点的二叉树的数量为Cn
• 三角形的分割：一个n边形的可能分割方式是Cn-2

4. 应用实例：

• 有效括号实例：给定n对括号，能够形成的有效括号序列的数量就是Cn
• 不同的二叉搜索树：对于n个不同的节点，构造不同的二叉搜索树的方案数位为Cn
• 多边形的非交叉三角剖分：一个n + 2边的多边形可以被分割成n个三角形的方法数为Cn

11.1 不同的二叉搜索树

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

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

解法一：Catalan数

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 + 1; i++) {for (int j = 0; j < i; j++) {dp[i] += dp[j] * dp[i - 1 - j];}}return dp[n];}
}

11.2 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

解法一：Catalan数

class Solution {public List<String> generateParenthesis(int n) {ArrayList<String>[] dp = new ArrayList[n + 1];dp[0] = new ArrayList<>(List.of(""));dp[1] = new ArrayList<>(List.of("()"));for (int j = 2; j < n + 1; j++) {dp[j] = new ArrayList<>();for (int i = 0; i < j; i++) {// i 对应的集合是内层要嵌套的括号，j - i - i对应的集合是平级要拼接的括号System.out.println("(%d, %d}\t", i, j - i - 1);for (String k1 : dp[i]) {for (String k2 : dp[j - 1 - i]) {               dp[j].add("(" + k1 + ")" + k2);}}}}return dp[n];}
}

解法二：递归

class Solution {public List<String> generateParenthesis(int n) {ArrayList<String> list = new ArrayList<>();StringBuilder sb = new StringBuilder();sb.append("(");dfs(list, sb, 1, 0, n);return list;}private void dfs(ArrayList<String> list, StringBuilder current, int open, int close, int n) {if (current.length() == 2 * n) {list.add(current.toString());return;}if (open < n) {current.append("(");dfs(list, current, open + 1, close, n);current.deleteCharAt(current.length() - 1);}if (close < open) {current.append(")");dfs(list, current, open, close + 1, n);current.deleteCharAt(current.length() - 1);}}
}

11.3 不同的出栈序列

n个元素进栈序列为：1、2、3、4、...，则有多少种出栈序列。

• n = 1时，有1种；
• n = 2时，有2种
• n = 3时，有5种
• n = 4时，如下图

class Solution {public int numPop(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i < n + 1; i++) {for (int j = 0; j < i; j++) {dp[i] += dp[j] * dp[i - 1 - j];}}return dp[n];}
}

11.4 买票找零问题

售票处售卖球票，每张票 50 元。有2n人前来买票

• 其中一半人手持 50 元钞票

• 另一半人手持 100 元钞票

若售票处开始没有任何零钱，问：有多少种排队方式，能够让售票顺畅进行。

解题思路：

• 把手持 50 元钞票的人视为左括号

• 把手持 100 元钞票的人视为右括号

• 左右括号合法配对，即先出现左括号，再出现右括号，就可以让售票顺畅执行

可以看到，问题又变成了求解 n 的卡特兰数

    public int numWays(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i < n + 1; i++) {for (int j = 0; j < i; j++) {dp[i] += dp[j] * dp[i - 1 - j];}}return dp[n];}

11.5 验证二叉树的前序序列化

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的

• 例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

注意：不允许重建树。

示例 1:

输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"输出: true

示例 2:

输入: preorder = "1,#"输出: false

示例 3:

输入: preorder = "9,#,#,1"输出: false

提示:

• 1 <= preorder.length <= 10^4
• preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成

解法一：每棵二叉树的空节点比非空节点个数多1

class Solution {public boolean isValidSerialization(String preorder) {String[] nodes = preorder.split(",");int diff = 1; // 初始化可用空位为1for (String node : nodes) {// 没读取一个节点，若为非空节点，空位减去1if (diff == 0) {// 没有了空位但还有节点return false;}if (!node.equals("#")) {// 每个非空节点增加一个空位diff++;} else {// 每个空节点会占用一个空位diff--;}}// 最终应该没有剩余的空位return diff == 0;}
}

或：

class Solution {public boolean isValidSerialization(String preorder) {String[] nodes = preorder.split(",");int diff = 1; // 初始空位数量，1个表示根节点可以在树中for (String node : nodes) {// 每读取一个节点，若为非空节点，空位减去 1if (--diff < 0) {return false; // 如果没有空位了，但还有节点，返回 false}if (!node.equals("#")) {diff += 2; // 非空节点生成两个新的空位}}return diff == 0; // 最终应该没有剩余的空位}
}

11.6 所有可能的满二叉树

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

示例 1：

输入：n = 7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

提示：

• 1 <= n <= 20

解法一：真二叉树的每个节点要么是叶子节点，要么有两个孩子

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<TreeNode> allPossibleFBT(int n) {List<TreeNode> result = new ArrayList<>();// 真二叉树的节点数量必须是奇数if (n % 2 == 0) {return result; // 如果是偶数，直接返回空列表}// 针对n=1的基础情况if (n == 1) {result.add(new TreeNode(0));return result;}// 尝试不同的左右子树组合for (int left = 1; left < n; left += 2) {int right = n - 1 - left; // 剩下的节点数// 递归生成左右子树List<TreeNode> leftTrees = allPossibleFBT(left);List<TreeNode> rightTrees = allPossibleFBT(right);// 组合左右子树生成真二叉树for (TreeNode leftChild : leftTrees) {for (TreeNode rightChild : rightTrees) {TreeNode root = new TreeNode(0); // 节点值为0root.left = leftChild;root.right = rightChild;result.add(root);}}}return result;}
}

12. 打家劫舍

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

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

示例 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 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

解法一：动态规划

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

13. 旅行商问题

package com.itheima.algorithms.dynamicprogramming;import java.util.Arrays;
import java.util.stream.Collectors;/*** 旅行商问题* 经过所有城市回到起点的最小花费*/
public class TravellingSalesmanProblem {/*北京->上海->武汉->西安->4x3x2 = 245x4x3x2 = 120...(n-1)!北京->上海->武汉->西安->北京西安->武汉->北京西安->上海->武汉->北京武汉->上海->北京武汉->上海->西安->北京西安->上海->北京g0  1  2  30  {0, 1, 2, 3}1  {1, 0, 6, 4}2  {2, 6, 0, 5}3  {3, 4, 5, 0}d(出发城市, 剩余城市集合) ==> 从出发城市开始，走完剩余城市，花费的最少代价d(0,1|2|3) => g[0][1] + d(1,2|3) => g[1][3] + d(3,2) => g[3][2] + d(2,空)g[2][0]=> g[1][2] + d(2,3) => g[2][3] + d(3,空)g[3][0]g[0][2] + d(2,1|3) => g[2][1] + d(1,3) => g[1][3] + d(3,空)g[3][0]=> g[2][3] + d(3,1) => g[3][1] + d(1,空)g[1][0]g[0][3] + d(3,1|2) => g[3][1] + d(1,2) => g[1][2] + d(2,空)g[2][0]=> g[3][2] + d(2,1) => g[2][1] + d(1,空)g[1][0]0   1   2   3    4   5    6    7     j 剩余城市集合0   1   2   1|2  3   1|3  2|3  1|2|30123i 出发城市000 没城市  0001 1号    1010 2号    2100 3号    4011 1和2   3101 1和3   5110 2和3   6111 1和2和3 7出发城市 i剩余城市集合 j遍历 j 时的变量 k （剩余的某一个城市)d(i, j) => min(g[i][k] + d(k, j去掉k)g[i][k] + d(k, j去掉k)g[i][k] + d(k, j去掉k))d(k,空) => 从k回到起点 => g[k][i]d(0,1|2) => g[0][1] + d(1,2)=> g[0][2] + d(2,1)d(1,1|2)d(2,1|2)d(3,1|2) => g[3][1] + d(1,2)=> g[3][2] + d(2,1)*/public static void main(String[] args) {int[][] graph = {{0, 1, 2, 3},{1, 0, 6, 4},{2, 6, 0, 5},{3, 4, 5, 0}};System.out.println(tsp(graph));}private static int tsp(int[][] g) {int m = g.length;  // 城市数目int n = 1 << (m - 1); // 剩余城市的组合数 2^(m-1)int[][] dp = new int[m][n];// 填充第0列for (int k = 0; k < m; k++) {dp[k][0] = g[k][0];}print(dp);// 填充后续列for (int j = 1; j < n; j++) {for (int i = 0; i < m; i++) {dp[i][j] = Integer.MAX_VALUE / 2;if(contains(j, i)) {// 剩余城市集合已包含出发城市，不合理continue;}// 填充单元格for (int k = 0; k < m; k++) {if(contains(j, k)) {// 只对剩余城市集合中的城市进行处理dp[i][j] = Integer.min(dp[i][j], g[i][k] + dp[k][exclude(j, k)]);}}}}print(dp);return dp[0][n - 1];}/*1|2|3  1 => 2|3111001 ^----110     2|31|2|3  2 => 1|3111010 ^----101   1|3*/private static int exclude(int set, int city) {return set ^ (1 << (city - 1));}/*2|3110  城市1是否存在    110001 &----000false110  城市2是否存在    011001 &----001true110  城市3是否存在    001001 &----001true110  城市4是否存在    000001 &----000false*/private static boolean contains(int set, int city) {// 判断set中是否已包含cityreturn (set >> (city - 1) & 1) == 1;}static void print(int[][] dist) {System.out.println("-------------------------");for (int[] row : dist) {System.out.println(Arrays.stream(row).boxed().map(x -> x >= Integer.MAX_VALUE / 2 ? "∞" : String.valueOf(x)).map(s -> String.format("%2s", s)).collect(Collectors.joining(",", "[", "]")));}}
}

14. 其他题目

14.1 编辑距离

给你两个单词 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')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

解法一：动态规划。时间复杂度和空间复杂度为O(mn)

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的操作数int[][] dp = new int[m + 1][n + 1];// 初始化dp数组for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {// word1为空，需插入j个字符dp[i][j] = j;} else if (j == 0) {// word2为空，需删除i个字符dp[i][j] = i;}}}// 填充dp数组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] = Math.min(Math.min(dp[i - 1][j] + 1, // 删除dp[i][j - 1] + 1), // 插入dp[i - 1][j - 1] + 1); // 替换}}}return dp[m][n];}
}

降维：时间复杂度O(mn)，空间复杂度O(n)

public class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// 确保 m <= n，方便后面的操作if (m > n) {String temp = word1;word1 = word2;word2 = temp;m = word1.length();n = word2.length();}// 使用一维数组来代替二维数组int[] dp = new int[n + 1];// 初始化 dp 数组for (int j = 0; j <= n; j++) {dp[j] = j; // 将空字符串转换为 word2 的前 j 个字符}// 更新 dp 数组for (int i = 1; i <= m; i++) {int prev = dp[0]; // 记录 dp[i-1][j-1]dp[0] = i; // 将 word1 的前 i 个字符转换为空字符串所需的操作数for (int j = 1; j <= n; j++) {int temp = dp[j]; // 保存 dp[i][j] 的当前值，用于后续替换计算if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[j] = prev; // 字符相等，无需操作} else {// 计算插入、删除、替换的最小操作数dp[j] = Math.min(Math.min(dp[j - 1] + 1, // 插入dp[j] + 1), // 删除prev + 1); // 替换}prev = temp; // 更新 prev 为当前 dp[j] 的旧值}}return dp[n]; // 返回将 word1 转换为 word2 的最小操作数}
}

14.2 买股票的最佳时机

给定一个数组 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。

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

解法一：执行耗时1ms

class Solution {public int maxProfit(int[] prices) {int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < minPrice) {minPrice = prices[i];}else if (prices[i] - minPrice > maxProfit) {maxProfit = prices[i] - minPrice;}}return maxProfit;}
}

解法二：动态规划。执行耗时4ms

class Solution {public int maxProfit(int[] prices) {// 如果价格数组为空或只有一个元素，无法进行交易if (prices.length < 2) {return 0;}// 定义动态规划数组int[] profit = new int[prices.length];profit[0] = 0; // 第一天没有利润int minPrice = prices[0]; // 初始化最低买入价格// 遍历价格数组for (int i = 1; i < prices.length; i++) {minPrice = Math.min(minPrice, prices[i - 1]); // 更新最低价格profit[i] = Math.max(profit[i - 1], prices[i] - minPrice); // 更新最大利润}return profit[prices.length - 1]; // 返回最后一天的最大利润}
}

14.3 组合总和Ⅳ

给你一个由 不同 整数组成的数组 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

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

解法一：动态规划

class Solution {public int combinationSum4(int[] nums, int target) {// 创建 dp 数组，大小为 target + 1int[] dp = new int[target + 1];dp[0] = 1; // 和为 0 的组合数为 1// 遍历从 1 到 targetfor (int i = 1; i <= target; i++) {// 对 nums 中的每个元素for (int num : nums) {// 如果 num 小于等于当前的目标 iif (i >= num) {dp[i] += dp[i - num]; // 更新组合数}}}return dp[target]; // 返回总和为 target 的组合数}
}