动态规划
介绍
**动态规划（Dynamic Programming, DP）**是一种用于解决复杂问题的算法思想。它将一个复杂问题分解成更小的子问题，通过保存子问题的结果，避免重复计算，从而提高算法的效率。动态规划特别适用于具有重叠子问题和最优子结构性质的问题。
动态规划的两个关键性质：
- 重叠子问题（Overlapping Subproblems）:问题可以被分解成相同的子问题，这些子问题在求解过程中会被多次用到。通过保存子问题的解，可以避免重复计算。例如，斐波那契数列的计算中，fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)，其中 fibonacci(n-1) 和 fibonacci(n-2) 会被多次计算。
- 最优子结构（Optimal Substructure）:一个问题的最优解包含其子问题的最优解。这意味着可以通过解决子问题的最优解来构造原问题的最优解。例如，求解最短路径问题时，子路径的最优解可以帮助找到整体路径的最优解。
动态规划的基本步骤：
定义状态:明确用哪些变量（状态）表示原问题和子问题。例如，求解最长公共子序列时，状态可以定义为 dp[i][j] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的最长公共子序列长度。
确定状态转移方程:确定如何通过子问题的解来得到原问题的解，即确定状态之间的关系。例如，对于最长公共子序列问题，如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始化:确定初始状态。例如，在求解斐波那契数列时，初始状态为 dp[0] = 0，dp[1] = 1。
计算结果:根据状态转移方程和初始状态，逐步计算出问题的最优解。
动态规划的应用：
最优化问题：如背包问题、最长递增子序列、最长公共子序列、最小编辑距离等。
计数问题：如计算不同路径、硬币组合问题等。
博弈问题：如石子游戏问题、打家劫舍问题等。
- 动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
- 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
- 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)
- 动态规划可以通过填表的方式来逐步推进，得到最优解.
背包问题
- 背包问题：有一个背包，容量为4磅 ， 现有如下物品
- 1.要求达到的目标为装入的背包的总价值最大，并且重量不超出
- 2，要求装入的物品不能重复
- 思路分析和图解
- 1.背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大
- 2.其中又分01背包和完全背包(完全背包指的是：每种物品都有无限件可用)
- 3.这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
- 4.每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果：
- (1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0
- (2) 当w[i]> j 时：v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略
- (3) 当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当 准备加入的新增的商品的容量小于等于当前背包的容量,
v[i-1][j]：上一个单元格的装入的最大值,(还没装i的值)
v[i] : 表示当前商品的价值,v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的最大值(装了i的值)
| 物品 | 重量 | 价格 |
|---|---|---|
| 吉他(G) | 1 | 1500 |
| 音响(S) | 4 | 3000 |
| 电脑(L) | 3 | 2000 |
public class KnapsackProblem {
public static void main(String[] args) {
int[] w = {1, 4, 3};//物品的重量
int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i]
int m = 4; //背包的容量
int n = val.length; //物品的个数
//v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
int[][] v = new int[n+1][m+1];
//记录放入商品的情况，定一个二维数组
int[][] path = new int[n+1][m+1];
//初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
for(int i = 0; i < v.length; i++) {
v[i][0] = 0; //将第一列设置为0
}
for(int i=0; i < v[0].length; i++) {
v[0][i] = 0; //将第一行设置0
}
//根据前面得到公式来动态规划处理
for(int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的
for(int j=1; j < v[0].length; j++) {//不处理第一列, j是从1开始的
//公式
if(w[i-1]> j) { // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
v[i][j]=v[i-1][j];
} else {
//说明:
//因为我们的i 从1开始的， 因此公式需要调整成
//v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
//为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
//把当前的情况记录到path
path[i][j] = 1;
} else {
v[i][j] = v[i - 1][j];
}
}
}
}
//输出最后我们是放入的哪些商品
//遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
// for(int i = 0; i < path.length; i++) {
// for(int j=0; j < path[i].length; j++) {
// if(path[i][j] == 1) {
// System.out.printf("第%d个商品放入到背包\n", i);
// }
// }
// }
int i = path.length - 1; //行的最大下标
int j = path[0].length - 1; //列的最大下标
while(i > 0 && j > 0 ) { //从path的最后开始找
if(path[i][j] == 1) {
System.out.printf("第%d个商品放入到背包\n", i);
j -= w[i-1]; //w[i-1]
}
i--;
}
}
}
70爬楼梯
爬楼梯需要n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法？
时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。
到达第 n 阶的方法数量 f(n) 等于到达第 n-1 阶的方法数量 f(n-1) 和到达第 n-2 阶的方法数量 f(n-2) 之和，即 f(n) = f(n-1) + f(n-2)。
f(n-2)，即到达第 n-2 阶的方法数。只需再爬2阶，方法数不变就可以到达n
f(n-1)，即到达第 n-1 阶的方法数。只需再爬2阶，方法数不变就可以到达n
f(n)，即到达第 n 阶的方法数。
class Solution {
public int climbStairs(int n) {
if(n == 1) return 1;
int[] dp = new int[n+1];
dp[1]=1;dp[2]=2;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
118杨辉三角
给定一个非负整数numRows生成「杨辉三角」的前 numRows 行。
时间复杂度：O(numRows^2)。
空间复杂度：O(1)。不考虑返回值的空间占用。
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
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(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
}
}
ret.add(row);
}
return ret;
}
}
198打家劫舍
小偷计划偷窃沿街的房屋内藏有的现金，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下能够偷窃到的最高金额。
示例1：输入：[1,2,3,1] 输出：4 解释：偷窃1号和3号房屋。偷窃到的最高金额=1+3=4
示例2：输入：[2,7,9,3,1] 输出：12 解释：偷窃1号、3号、5号房屋。偷窃到的最高金额=2+9+1=12
时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
空间复杂度：O(n)。
思路：如果偷当前房屋i则金额为i-2和i的和，如果不偷的话则金额为i-1，每次比较这2种情况就行
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
279完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2：输入：n = 13 输出：2 解释：13 = 4 + 9
[ \min_{x \in \mathbb{R}} \left( x^2 - 2x + 1 \right) = \frac{2+\sqrt{8}}{2} ]
时间复杂度：O(n√n)，其中 n 为给定的正整数。状态转移方程的时间复杂度为 O(√n)，共需要计算 n 个状态，因此总时间复杂度为 O(n√n)。
空间复杂度：O(n)。我们需要 O(n) 的空间保存状态。
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
// 初始化dp数组，假设所有值都未能被正确计算过
Arrays.fill(dp, n+1);
dp[0] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j*j<=i;j++){
dp[i] = Math.min(dp[i],dp[i-j*j] + 1);
}
}
return dp[n];
}
}
322零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。我们一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
空间复杂度：O(S)。数组 dp 需要开长度为总金额 S 的空间。
public class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
139单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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
时间复杂度：O(n^2) ，其中 n 为字符串 s 的长度。我们一共有 O(n) 个状态需要计算，每次计算需要枚举 O(n) 个分割点，哈希表判断一个字符串是否出现在给定的字符串列表需要 O(1) 的时间，因此总时间复杂度为 O(n
^2)。
空间复杂度：O(n) ，其中 n 为字符串 s 的长度。我们需要 O(n) 的空间存放 dp 值以及哈希表亦需要 O(n) 的空间复杂度，因此总空间复杂度为 O(n)。
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
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
时间复杂度：O(n^2)，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n^2)。
空间复杂度：O(n)，需要额外使用长度为 n 的 dp 数组。
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.length; 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);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}
152乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1: 输入: nums = [2,3,-2,4] 输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:输入: nums = [-2,0,-1] 输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
记 nums 元素个数为 n。
时间复杂度：程序一次循环遍历了 nums，故渐进时间复杂度为 O(n)。
空间复杂度：优化后只使用常数个临时变量作为辅助空间，与 n 无关，故渐进空间复杂度为 O(1)。
class Solution {
public int maxProduct(int[] nums) {
int length = nums.length;
long[] maxF = new long[length];//每个元素结尾的最大和最小乘积的子数组
long[] minF = new long[length];
for (int i = 0; i < length; i++) {
maxF[i] = nums[i];
minF[i] = nums[i];
}
for (int i = 1; i < length; ++i) {
//maxF[i] 为 max(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i])，用于计算可能的最大值。
//minF[i] 为 min(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i])，用于计算可能的最小值。
maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
if (minF[i] < (-1 << 31)) {
minF[i] = nums[i];
}
}
int ans = (int) maxF[0];
for (int i = 1; i < length; ++i) {
ans = Math.max(ans, (int) maxF[i]);
}
return ans;
}
}
416分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：输入：nums = [1,5,11,5] 输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：输入：nums = [1,2,3,5] 输出：false
解释：数组不能分割成两个元素和相等的子集。
时间复杂度：O(n×target)，其中 n 是数组的长度，target 是整个数组的元素和的一半。需要计算出所有的状态，每个状态在进行转移时的时间复杂度为 O(1)。
空间复杂度：O(target)，其中 target 是整个数组的元素和的一半。空间复杂度取决于 dp 数组，在不进行空间优化的情况下，空间复杂度是 O(n×target)，在进行空间优化的情况下，空间复杂度可以降到 O(target)。
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
if (n < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (int num : nums) {
sum += num;
maxNum = Math.max(maxNum, num);
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
//用于表示是否存在一个子集，其和等于数组索引 j/target
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int i = 0; i < n; i++) {
int num = nums[i];
//正向遍历则在同一轮循环中，dp[j - num] 可能已经被本轮循环的某个元素更新过了，导致错误地使用了当前元素多次。
//逆向遍历的原因是为了防止在同一轮迭代中重复使用某个元素。
for (int j = target; j >= num; --j) {
dp[j] |= dp[j - num];
//表示：如果之前已经存在一个和为 j 的子集（dp[j] 为 true），
//或者通过加入 num 后能找到一个和为 j 的子集（dp[j - num] 为 true），那么 dp[j] 就应该为 true。
}
}
return dp[target];
}
}
32最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：输入：s = ")()())"输出：4 解释：最长有效括号子串是 "()()"
示例 3：输入：s = "" 输出：0
时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。
空间复杂度： O(n)。我们需要一个大小为 n 的 dp 数组。
假设字符串：()()(())
dp[i - 1] 仅表示 s[i - 1] 结尾的有效括号子串的长度。这个长度仅由 s[i - dp[i - 1]] 到 s[i - 1] 的子串贡献，它并不包括更前面的部分。
dp[i - dp[i - 1] - 2] 表示在 s[i - dp[i - 1] - 2] 位置结束的有效括号子串的长度。
如果 s[i - dp[i - 1] - 1] 是 (，则 s[i] 和 s[i - dp[i - 1] - 1] 配对，这样就可以把 dp[i - 1] 前面的部分（即 dp[i - dp[i - 1] - 2]）也包含进来，形成更长的有效括号子串。
class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
int[] dp = new int[s.length()];//以第 i 个字符结尾的最长有效括号子串的长度。
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {//对应i=1和3
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;//2表示"()"的长度为2
//i - dp[i - 1] > 0确保在访问 s.charAt(i - dp[i - 1] - 1) 时，不会数组越界
//i-dp[i-1]-1求的是去掉成对括号后的前一个字符串，并判断是否等于'('，如果相等则+2
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {//对应i=7时
//意味着在 dp[i - 1] 之前还有一个有效的括号。
//总数=前一个最长有效括号子串长度+本次2+前前最长有效括号子串长度，因为(之前可能还有子串
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
}
62不同路径
一个机器人位于一个 m x n 网格的左上角,每次只能向下或者向右移动一步试图达到网格的右下角。总共有多少条不同的路径？
时间复杂度：O(mn)。
空间复杂度：O(mn)，即为存储所有状态需要的空间。注意到 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))。
class Solution {
public int uniquePaths(int m, int n) {
int[][] f = new int[m][n];
//第一列的所有格子（即 (i,0)）的路径数量都被初始化为 1。
//因为在网格的第一列，从起点 (0,0) 到达任意一个 (i,0) 的路径只有一种：一直向下移动。
for (int i = 0; i < m; ++i) {
f[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
f[0][j] = 1;
}
//到达 (i,j) 的路径数量 f[i][j] 是这两个格子的路径数量之和：f[i][j] = f[i - 1][j] + f[i][j - 1]。
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
}
64最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。
示例 1：输入：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)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 dp 的每个元素的值。
空间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dp，和网格大小相同。
空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, columns = grid[0].length;
int[][] dp = new int[rows][columns];
dp[0][0] = grid[0][0];
//这里填充 dp 的第一列（即 (i,0)），每个格子只能从它上面的格子 (i-1,0) 走过来。
//因此，dp[i][0] 是上面格子的最小路径和加上当前格子的权重值。
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
//到达 (i,j) 的最小路径和 dp[i][j] 是上面或左边两个格子路径和中的较小值再加上当前格子的权重值：
//dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][columns - 1];
}
}
5最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：输入：s = "babad"输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：输入：s = "cbbd" 输出："bb"
时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
空间复杂度：O(n^2)，即存储动态规划状态需要的空间。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();//因为单个字符或空字符串本身就是回文串。
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示字符串 s 中从 i 到 j 的子串 s[i..j] 是否为回文串
boolean[][] dp = new boolean[len][len];
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界，即 L = j - i + 1 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
//当子串长度为 2 或 3 (j - i < 3) 时，s[i..j] 一定是回文子串，因为两个相等的字符（例如 "aa"）或者中间只有一个字符（例如 "aba"）都构成回文。
//对于更长的子串，s[i..j] 是否为回文取决于 s[i+1..j-1] 是否为回文（即 dp[i + 1][j - 1] 的值）。
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
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 。
时间复杂度：O(mn)，其中 m 和 n 分别是字符串 text1和 text2的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算。
空间复杂度：O(mn)，其中 m 和 n 分别是字符串 text 1和 text 2的长度。创建了 m+1 行 n+1 列的二维数组 dp。
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
char c1 = text1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = text2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
//如果 c1 和 c2 不相等，说明此时只能继承前一个子问题的最优解
//dp[i-1][j] 表示忽略 text1[i-1] 字符的情况。
//dp[i][j-1] 表示忽略 text2[j-1] 字符的情况。
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
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')
时间复杂度 ：O(mn)，其中 m 为 word1 的长度，n 为 word2 的长度。
空间复杂度 ：O(mn)，我们需要大小为 O(mn) 的 D 数组来记录状态值。
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
// 有一个字符串为空串
//如果其中一个字符串为空串，则最小编辑距离直接等于另一个字符串的长度，
//即需要进行的插入或删除操作的次数为 n + m。
if (n * m == 0) {
return n + m;
}
// DP 数组
int[][] D = new int[n + 1][m + 1];
// 边界状态初始化
//当 word2 为空串时，需要删除 word1 的全部字符，所以 D[i][0] = i。
//当 word1 为空串时，需要插入 word2 的所有字符，所以 D[0][j] = j。
for (int i = 0; i < n + 1; i++) {
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++) {
D[0][j] = j;
}
// 计算所有 DP 值
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
int left = D[i - 1][j] + 1;// 删除操作 将 word1[0..i-1] 的第 i 个字符删除，然后与 word2[0..j] 比较。
int down = D[i][j - 1] + 1;// 插入操作 在 word1[0..i] 的结尾处插入一个字符，使得 word1[0..i] 和 word2[0..j-1] 匹配。
int left_down = D[i - 1][j - 1];// 替换操作 将 word1[0..i-1] 和 word2[0..j-1] 进行替换，如果字符不同则需要一次替换操作，left_down 的值加 1。
if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
left_down += 1;
}
//D[i][j] 取三者中的最小值，表示三种操作中编辑距离最小的情况。
D[i][j] = Math.min(left, Math.min(down, left_down));
}
}
return D[n][m];
}
}