动态规划算法题1

动态规划做题步骤

1. 确定状态表示：dp表中某一个位置中的值所表示的含义就是状态表示
2. 根据状态表示推导状态转移方程：dp[i]等于什么状态转移方程就是什么，用之前或者之后的状态，推导出dp[i]的值
3. 初始化(防止越界)：根据状态转移方程填表，保证填表时候不越界
4. 确定填表顺序：填写当前状态的时候，所需要的状态必须都已计算过
5. 返回结果：结合题目要求+状态表示

三步问题

面试题 08.01. 三步问题 - 力扣（LeetCode）

状态表示为：以i位置结尾，得到该题状态表示为dp[i]走到第i阶楼梯的走法总数

状态转移方程：状态转移方程以位置的状态最近一步来划分问题， 当对于第 i 阶楼梯，可以从i-3阶走3步上来，或者从 i-2阶走2步上来， 或者从 i -1阶走1步上来。 因此状态转移方程为

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]。

步骤：

• 判断边界情况：由于状态转移方程需要前三个元素的状态表示，所以当n<=3时直接返回推出来的结果接口
• 创建dp表
• 初始化dp表：初始化前三个元素值（防止越界）
• 根据状态转移方程进行填表：dp[i] = dp[i-3] + dp[i-2] + dp[i-1]。

状态转移方程描述：

dp[i-3] 表示所有走到 i-3 阶的走法，然后一次性跨 3 步到 i 阶。
dp[i-2] 表示所有走到 i-2 阶的走法，然后一次性跨 2 步到 i 阶。
dp[i-1] 表示所有走到 i-1 阶的走法，然后一次性跨 1 步到 i 阶。
不需要考虑 "从 i-3 阶分多步（如 1+1+1 或 1+2 等）走到 i 阶"
因为 dp[i-3] 已经包含了所有可能的走法（包括 1+1+1、1+2、2+1、3 等），而最后一步必须是 +3（即一次性跨 3 步）。

如果从 i-3 阶分多步走到 i 阶（比如 1+1+1），那么这些情况已经被 dp[i-1] 和 dp[i-2] 覆盖了：i-3 → i-2 → i-1 → i（即 1+1+1）已经被 dp[i-1] 包含（因为 dp[i-1] 包含了所有走到 i-1 的走法，最后一步是 +1）。
i-3 → i-1 → i（即 2+1）已经被 dp[i-1] 包含（因为 dp[i-1] 包含了所有走到 i-1 的走法，最后一步是 +1）。
i-3 → i（即 3）才是 dp[i-3] 贡献的部分。
dp[i-3] 贡献的是最后一步跨 3 步的走法。
dp[i-2] 贡献的是最后一步跨 2 步的走法。
dp[i-1] 贡献的是最后一步跨 1 步的走法。
这样计算不会重复也不会遗漏，因为 dp[i-1]、dp[i-2]、dp[i-3] 已经包含了所有可能的走法组合，而最后一步的步数决定了它们属于哪个部分。

class Solution {public int waysToStep(int n) {//判断边界情况if(n == 1 || n == 2) return n;if(n == 3) return 4;// 1. 创建动态规划表dp，dp[i]表示走到第i阶楼梯的走法总数int[] dp = new int[n+1];// 2. 初始化dp表的前三个值（基础情况）dp[1] = 1; dp[2] = 2; dp[3] = 4;// 3.根据动态转移方程进行填表// 由于数字可能很大，每次相加后都取模1000000007防止溢出for(int i = 4; i <=n; i++){dp[i] = ((dp[i - 3] + dp[i - 2])%1000000007 + dp[i - 1])%1000000007;}// 4. 返回结果：第n阶楼梯的走法总数return dp[n];}
}   

使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

解法一：

1. 状态表示：以i位置为结尾，dp[i]表示到达 i 位置的时候最小花费。

2. 状态转移方程推导：
在计算 dp[i] 时，存在两种可行的到达方式：
先到达第 i - 1 个位置，接着支付 cost[i - 1] 的费用，然后向前走一步到达第 i 个位置。这种情况下，到达第 i 个位置的最小花费为 dp[i - 1] + cost[i - 1]。
先到达第 i - 2 个位置，接着支付 cost[i - 2] 的费用，然后向前走两步到达第 i 个位置。这种情况下，到达第 i 个位置的最小花费为 dp[i - 2] + cost[i - 2]。
由于 dp[i] 代表的是到达第 i 个位置的最小花费，所以我们需要取上述两种情况中的最小值，即 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。

3. 初始化操作：
在进行状态数组 dp 的填充时，当计算 dp[0] 和 dp[1] 时，由于需要参考前两个位置的状态，会出现越界问题。因此，需要对这两个元素进行初始化。

4. 填表顺序：
状态数组 dp 的填充顺序是从左到右，也就是依次计算 dp[0]、dp[1]、dp[2] 直至 dp[n]。

5. 返回值：最终，我们直接返回 dp[n]，它就是到达第 n 个位置时的最小花费。

class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length; // 获取楼梯的总阶数// 1. 创建动态规划表dp，dp[i]表示到达第i阶楼梯的最小花费// 数组长度为len+1，因为我们要计算到达顶层（即第len阶）的最小花费int[] dp = new int[len+1];// 2. 初始化dp表 起点花费为0，数组默认为0 省略初始化// 3. 根据状态转移方程填表 从第2阶开始计算，直到第len阶（顶层）for(int i = 2; i <= len; i++){// 计算从第i-1阶跨1步到第i阶的总花费int tmp1 = dp[i - 1] + cost[i - 1];// 计算从第i-2阶跨2步到第i阶的总花费int tmp2 = dp[i - 2] + cost[i - 2];// 取两种方式中的较小值作为到达第i阶的最小花费dp[i] = Math.min(tmp1, tmp2);}// 4. 返回结果 dp[len]表示到达顶层（第len阶）的最小花费return dp[len];}
}

解法二：解法一采用以 i 位置为结尾的思想结合题目条件得到状态表示，而解法二则是基于以 i 位置为起点的思想结合题目来构建状态表示。

1.状态表示定义：定义 dp[i] 为从第 i 个位置出发，到达楼顶所需的最小花费。

2.状态转移方程推导：
在计算 dp[i] 时，存在两种可行的行进方式：
支付 cost[i] 的费用，然后向前走一步到达第 i + 1 个位置，之后从该位置出发到达楼顶。这种情况下，从第 i 个位置出发到达楼顶的最小花费为 cost[i] + dp[i + 1]。
支付 cost[i] 的费用，然后向前走两步到达第 i + 2 个位置，之后从该位置出发到达楼顶。这种情况下，从第 i 个位置出发到达楼顶的最小花费为 cost[i] + dp[i + 2]。
由于 dp[i] 代表的是从第 i 个位置出发到达楼顶的最小花费，所以我们需要取上述两种情况中的最小值，即 dp[i] = min(cost[i] + dp[i + 1], cost[i] + dp[i + 2])。

3.初始化操作：
因为在状态转移过程中需要用到后续两个位置的状态值，所以要对最后两个下标对应的元素进行初始化。到达楼顶不需要额外花费，其最小花费为 0，所以 dp 数组的大小与 cost 数组相同即可。最后两个位置的最小花费就是当前位置的费用。

4.填表顺序：
状态数组 dp 的填充顺序是从右到左，也就是依次计算 dp[n - 1]、dp[n - 2] 直至 dp[0]。

5.返回值：
由于 dp[i] 表示从第 i 个位置出发到达楼顶的最小花费，而整个行程可以从第 0 个位置或者第 1 个位置开始，所以最终应返回 dp[0] 和 dp[1] 中的最小值。

class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length; // 获取楼梯的总台阶数// 1. 创建动态规划表dp，dp[i]表示从第i阶台阶出发到达楼顶的最小花费// 这里采用从后向前填充的方式，因此数组长度与cost相同int[] dp = new int[len];// 2. 初始化dp表// 最后一级台阶（len-1）的最小花费就是cost[len-1]，因为必须支付该台阶费用才能到达楼顶// 倒数第二级台阶（len-2）可以选择直接跨两步到楼顶，或先到len-1再跨一步// 因此取两者中的较小值加上当前台阶的花费dp[len - 1] = cost[len - 1]; dp[len - 2] = cost[len - 2];// 3. 根据状态转移方程逆向填表（从倒数第三级台阶开始向前计算）// 状态转移方程：dp[i] = min(dp[i+1], dp[i+2]) + cost[i]// 表示从第i阶出发的最小花费等于下一步（i+1或i+2）的最小花费加上当前台阶的花费for(int i = len - 3; i >= 0; i--){dp[i] = Math.min(dp[i+1], dp[i+2]) + cost[i];}// 4. 返回结果// 根据题意可以从第0级或第1级台阶开始，因此返回两者中的较小值return dp[0] < dp[1] ? dp[0] : dp[1];}
}

解码方式

91. 解码方法 - 力扣（LeetCode）

1.状态表示：dp[i]表示以字符串s中第i位置结尾时，解码方法的总数。

2.状态转移方程推导：对字符串第i个位置进行解码，存在两种可行的情况：

第一种：
当s[i]能够单独进行解码时，也就意味着s[i]代表一个有效的字符编码。此时，以i位置结尾的解码方法总数，与以i - 1位置结尾的解码方法总数是相同的，即dp[i]可以从dp[i - 1]推导而来。如果s[i]不能单独解码，例如s[i]为字符0且它前面没有可与之组合的字符形成合法编码，那么所有基于此位置的局部解码尝试都是无效的。由于我们关注的是全局的解码数，所以这种无效情况在后续推导中需要避免。

第二种：

当s[i - 1]和s[i]组合起来进行解码时，它们所构成的数字s[i - 1] * 10 + s[i]必须在10到26这个闭区间内。这是因为在合法的解码规则中，不能出现前导0。如果组合数字在0到9之间，就说明存在前导0，不符合解码要求。当s[i - 1]和s[i]成功解码时，以i位置结尾的解码方法总数，就等于以i - 2位置结尾的解码方法总数，即dp[i]可以从dp[i - 2]推导而来。

综合以上两种情况，当两种解码方式都可以时，dp[i]等于dp[i-2]和dp[i-1]之和。

注意：只有在解码成功的前提下，才进行相应的累加操作

3.初始化：为了保证填表时不越界，所以需要初始化dp[i-1]和dp[i-2]所涉及的位置，即下标0和下标1处的元素。

初始化dp[0]

• 根据状态表示，dp[0]表示以0位置结尾的解码方式总数。当s[0]不等于0时，s[0]可以单独构成一种合法的解码方式，因此dp[0]初始化为1。若s[0]等于0，则表示解码失败.

初始化dp[1],存在以下三种情况：

• 当s[1]等于0时，说明解码失败.
• 当s[1]能够单独解码，且s[0]与s[1]不能组合解码时，dp[1]为1。例如，当s[0]和s[1]都在1到9之间，且s[0] * 10 + s[1]不在10到26的范围内时，只有一种单独解码的方式。
• 当s[1]既能单独解码，又能与s[0]组合解码时，dp[1]为2。

4.填表顺序：从左往右

5.返回结果：根据状态表示，dp[n-1]表示以字符串最后一个位置结束的解码方式总数，因此直接返回dp[n-1]即可。

class Solution {public int numDecodings(String s) {char[] arr = s.toCharArray();int n = arr.length;// 1. 创建dp表，dp[i]表示以i位置结尾时，解码方法的总数int[] dp = new int[n];// 2. 初始化dp表    第一个字符不为'0'，有1种解码方式if(arr[0] != '0') dp[0] = 1;// 处理字符串长度为1的边界情况 if(n == 1) return dp[0]; // 初始化第二个位置 当前一个字符和当前字符都不为0则表示有一种解码方式if(arr[1] != '0' && arr[0]!='0') dp[1] += 1;//前两个字符组合解码（必须在10-26之间）则又有一种解码方式int t = (arr[0] - '0') * 10 + arr[1] - '0';if( t >= 10 && t <= 26) dp[1] += 1;// 3.根据状态转移方程进行填表for(int i = 2; i < n; i++){// 情况1：当前字符单独解码（必须非'0'）if(arr[i] != '0') dp[i] += dp[i-1];// 情况2：当前字符和前一个字符组合解码int tt = (arr[i-1] - '0') * 10 + arr[i] - '0';if( tt >= 10 && tt <= 26) dp[i] += dp[i - 2];}// 4.返回结果return dp[n-1];}
}

优化初始化：

上述解码方式计数问题中，可以通过添加虚拟节点的方式，对初始化过程进行优化。原本在初始化dp[1]时，其判断逻辑体中的条件一致，造成了代码逻辑的冗余。

添加虚拟节点的目的是为了统一初始化逻辑，减少重复判断，而且后续填表计算依赖于前面节点的值，所有虚拟节点的值设置必须确保整个填表过程的正确性。

初始化操作调整：只需要对虚拟节点和原数组中下标为0位置对应的dp节点进行初始化。原本对下标为1位置节点的初始化操作被省略，该位置的值将在后续循环中，依据统一的状态转移方程进行计算。

下标映射调整：因为添加了头部虚拟节点，在访问原字符串来计算dp值时，所有原字符串的下标都需要减1。这确保了dp数组与原字符串在位置上的正确对应关系。
结果返回：由于dp数组增加了一个虚拟节点，最终的结果只需返回dp[n]即可。其中n为原字符串长度对应的dp数组下标，这样便能得到原字符串的解码方法总数。

class Solution {public int numDecodings(String s) {char[] arr = s.toCharArray();int n = arr.length;// 1. 创建dp表，dp[i]表示前i+1个字符的解码方式数int[] dp = new int[n + 1];dp[0] = 1;if(arr[0] != '0') dp[1] = 1;// 3.根据状态转移方程进行填表for(int i = 2; i <= n; i++){// 情况1：当前字符单独解码（必须非'0'）if(arr[i - 1] != '0') dp[i] += dp[i-1];// 情况2：当前字符和前一个字符组合解码int tt = (arr[i-2] - '0') * 10 + arr[i - 1] - '0';if( tt >= 10 && tt <= 26) dp[i] += dp[i - 2];}// 4.返回结果return dp[n];}
}

不同路径

62. 不同路径 - 力扣（LeetCode）

在解决路径计算问题时，引入虚拟节点，这一举措极大简化了边界情况的处理。最初， dp[i][j] 用于表示抵达坐标 (m, n) 的路径总数。但随着虚拟节点的引入，下标映射需进行相应调整。

1. 状态表示：将 dp[i - 1][j - 1] 定义为抵达坐标 (m, n) 的总路径数，即以 i 位置为路径终点。

2. 状态转移方程推导：考虑到机器人每次仅能向下或向右移动一格， dp[i][j] 所代表的总路径数，应为其上方节点和左方节点的路径数之和。而根据题目要求机器人路径不能包含任何有障碍物的格子，所以该状态转移方程分成两种情况。

第一种情况：[i,j]位置为障碍物，说明从上或从右都到不了该位置，该位置就为0

第二种情况：没有障碍物，依据状态表示，上方节点的总路径数为 dp[i - 1][j] ，左方节点的总路径数为 dp[i][j - 1] ，因此状态转移方程为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。

3. 初始化操作：在填充状态数组 dp 时，若按照既定的状态转移方程计算 dp[0][1] ，会导致数组越界。所以，在状态数组 dp 的最上方和最左侧各添加一层虚拟节点。由于起始节点需被赋值为1，因此只需将 dp[1][0] 或 dp[0][1] 其中之一初始化为1即可。

4. 填表顺序：在填充状态数组 dp 时，按照从左到右的顺序依次计算每个元素，确保每个节点的路径数能依据已计算的相邻节点得出。

5. 返回值：经过上述步骤的计算， dp[m][n] 即为抵达坐标 (m, n) 的总路径数，直接返回该值。

class Solution {public int uniquePaths(int m, int n) {// 1. 创建 dp 表，由于引入了虚拟节点dp[i][j] 表示到达 (i-1, j-1) 的路径数,//    这里使用 (m+1) × (n+1) 的数组，方便边界处理，m=0或n＝0时均为虚拟节点int[][] dp = new int[m+1][n+1];// 2.初始化// 关键初始化：让 dp[1][1] = dp[0][1] + dp[1][0] = 1 + 0 = 1// 这样 dp[1][1] 表示到达 (0,0) 的路径数为 1（起点）dp[0][1] = 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] += dp[i][j-1];// 左方路径数}}// 4. 返回结果：dp[m][n] 表示到达 (m-1, n-1) 的路径数return dp[m][n];}
}

按摩师

面试题 17.16. 按摩师 - 力扣（LeetCode）

1.状态表示：最初，定义dp[i]为选择到i位置时的最长预约时长。为更细致地解决问题，进一步将dp[i]划分为两个状态数组：

• f[i]：表示选择到i位置时，nums[i]必定被选择的情况下，此时的最长预约时长。
• g[i]：表示选择到i位置时，nums[i]不被选择的情况下，此时的最长预约时长。

2.状态转移方程
计算f[i]：由于f[i]要求必须选择nums[i]，那么前一个位置必然不能选择，依据状态表示，前一个位置不选时的最大预约时长由g[i - 1]表示。因此，f[i] = g[i - 1] + nums[i] 。
计算g[i]：g[i]表示不选择nums[i]，对于前一个位置i - 1，既可以选择也可以不选择，具体分为以下两种情况：

• 若前一个位置选择，即取f[i - 1]。
• 若前一个位置不选择，即取g[i - 1]。

为获取最长预约时长，g[i] = max(f[i - 1], g[i - 1])。

3.初始化操作：根据状态转移方程，计算过程仅需知道前一个元素的状态，因此只需对起始位置0进行初始化。

• 初始化f[0]：因为f数组表示必选当前元素的情况，所以f[0] = nums[0]。
• 初始化g[0]：由于g数组表示不选当前元素的情况，所以g[0] = 0。

4.填表顺序：在填充状态数组时，按照从左向右的顺序，同步填充f和g两个数组，确保每个位置的状态值能依据已计算的前一个位置得出。

5.返回结果：题目要求计算最长预约时长，只需返回f[n - 1]和g[n - 1]中的较大值，该值即为最终所求的最长预约时长。

class Solution {public int massage(int[] nums) {int n = nums.length;if(n == 0) return 0; // 边界情况：无预约时直接返回0// 1.创建dp表// f[i]：选择第i个预约时的最大总时长// g[i]：不选择第i个预约时的最大总时长int[] f = new int[n];int[] g = new int[n];// 2.初始化f[0] = nums[0];  // 选择第0个预约，时长为nums[0]// 3.根据状态转移方程进行填表for(int i = 1; i < n; i++){// 选择第i个预约：必须不选第i-1个预约，所以加上g[i-1]f[i] = g[i - 1] + nums[i];// 不选择第i个预约：可以选择或不选第i-1个预约，取最大值g[i] = Math.max(g[i - 1], f[i - 1]);}// 4. 返回结果：最终选择或不选最后一个预约的最大值return Math.max(f[n-1], g[n-1]);}
}

最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

1.状态表示：定义dp[i]，它表示以位置i结尾的所有子数组中，元素总和的最大值。

2.状态转移方程推导：
情况一：考虑以位置i结尾的子数组中，仅包含nums[i]这一个元素的情形。在这种情况下，dp[i]就等于nums[i]。
情况二：当以位置i结尾的子数组长度大于1时，它可以看作是以位置i - 1结尾的最大子数组和dp[i - 1]，再加上当前元素nums[i]。
综合以上两种情况，dp[i]取二者的最大值，即状态转移方程为dp[i] = max(nums[i], dp[i - 1] + nums[i])。该方程确保dp[i]始终是符合定义的最大子数组和。

3.初始化：状态转移方程依赖于dp[i - 1]，当i = 0时，dp[-1]并不存在，会导致越界问题。因此，需要对dp[0]进行初始化。由于此时数组中仅有nums[0]一个元素，所以dp[0] = nums[0]。

4.填表顺序：根据状态转移方程，dp[i]的计算仅依赖于dp[i - 1]，因此按照从左到右的顺序依次计算dp数组的元素，能够确保在计算每个dp[i]时，所需的dp[i - 1]已经计算完成。

5.返回结果：需要注意，dp[i]仅表示以位置i结尾的最大子数组和，而整个数组的最大子数组和不一定以最后一个位置结尾。因此，返回结果应该是dp数组中的最大值，这个值才是原问题的答案。

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;// 1. 创建一个dp数组，用于保存以每个位置结尾的最大子数组和int[] dp = new int[n];// 2. 初始化dp数组的第一个元素，即以nums[0]结尾的最大子数组和就是nums[0]本身dp[0] = nums[0];int max = dp[0]; ///用于记录全局的最大子数组和 初始化最大值为第一元素// 3. 根据状态转移方程填充dp数组// 状态转移方程：dp[i] = max(nums[i], dp[i - 1] + nums[i])// 表示以nums[i]结尾的最大子数组和，要么是nums[i]本身，要么是之前的最大子数组和加上nums[i]for(int i = 1; i < n; i++){dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);max = Math.max(max,dp[i]);}// 4. 返回全局的最大子数组和return max;}
}

最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

1. 状态表示：dp[i]表示以i位置为结尾的所有子序列中，最长递增子序列的长度。

2. 状态转移方程：基础情况和递推情况。

在基础情况下，每个元素自身构成一个长度为1的子序列，即dp[i]=1

在递推情况下，需要考察前面所有小于当前元素的子序列，从中选取最长的进行扩展。具体来说，对于0到i-1范围内的每个j，当nums[j]<nums[i]时，将nums[i]接在以nums[j]结尾的子序列后面，此时dp[i] = max(dp[i], dp[j]+1)。

3. 初始化：将整个dp数组初始化为1，这样既包含了基础情况，又为后续的递推计算提供了正确的初始值。

4. 填表顺序：从左向右

5. 返回值：最终结果需要返回dp数组中的最大值，因为最长递增子序列可能以数组中任意一个元素结尾。这与许多动态规划问题中直接取最后一个元素作为结果的做法有所不同，需要特别注意。

class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;// 1.创建dp表dp[i] 表示以nums[i]结尾的最长递增子序列的长度int[] dp = new int[n];// 2.初始化// 因为每个元素自身都可以构成一个长度为1的递增子序列，所以将dp数组初始化为1Arrays.fill(dp,1);// 记录当前找到的最长递增子序列的长度，初始值为1（单个元素的情况）int max = 1;// 3.根据状态转移方程填表// 外层循环遍历数组，计算以每个元素结尾的最长递增子序列的长度for(int i = 1; i < n; i++){// 内层循环用于比较当前元素nums[i]与前面的元素nums[j]for(int j = 0; j < i; j++){if(nums[j] < nums[i]) {//如果nums[j] < nums[i]，那么以nums[i]结尾的递增子序列长度可以在以nums[j]结尾的递增子序列长度基础上加1dp[i] = Math.max(dp[j]+1,dp[i]);}}// 更新全局的最长递增子序列的长度max = Math.max(max,dp[i]);}return max;}
}

回文子串

647. 回文子串 - 力扣（LeetCode）

1. 状态表示：dp[i[j]为字符串从下标i到下标j的子串是否为回文子串。

2. 状态转移方程：可以分为两种情况，第一种情况是当s[i]不等于s[j]时，该子串必定不是回文串，直接设置dp[i][j]为false。

第二种情况是当s[i]等于s[j]时，又细分为三种子情况：当i和j重合时，即单个字符必定是回文串；当i和j相邻时，两个相同字符组成的子串也是回文串；当i和j不相邻时，该子串的回文性质取决于其内部子串dp[i+1][j-1]的回文状态。

3. 初始化：初始化方面，由于只需要考虑i小于等于j的情况，且单个字符的情况已经通过状态转移方程处理为true，因此不需要额外的初始化步骤。

4. 填表顺序：填表顺序采用从下往上的方式逐行填写，即i从字符串末尾向前遍历。这种顺序确保了在计算dp[i][j]时，其依赖的子问题dp[i+1][j-1]已经被正确计算出来。

5. 返回值：最终结果是统计dp表中所有为true的个数，这代表了原字符串中所有可能的回文子串数量。需要注意的是，这里的返回值不是某个特定的dp值，而是整个表中满足条件的累计总数。

class Solution {public int countSubstrings(String s) {int n = s.length();// 1. 创建动态规划表dp[i][j]，表示s[i...j]是否为回文子串boolean[][] dp = new boolean[n][n];int ret = 0; // 统计回文子串总数// 2. 填表过程：从下往上(i从n-1到0)，从左往右(j从i到n-1)for(int i = n - 1; i>=0; i--){for(int j = i; j < n; j++){// 3. 状态转移：//    当首尾字符相等时，若子串长度<=2直接为回文，//    否则取决于内部子串dp[i+1][j-1]是否为回文if(s.charAt(i) == s.charAt(j))dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;if(dp[i][j]) ret++;}}return ret;}
}

最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）
1. 状态表示：设dp[i][j]表示第一个字符串的前i个字符（即[0,i]区间）和第二个字符串的前j个字符（即[0,j]区间）的最长公共子序列的长度。

2. 状态转移方程：状态转移方程需要考虑两种情况。第一种情况是当两个字符串的当前字符相等时（即s1[i] == s2[j]），这意味着当前字符必定是最长公共子序列的一部分。因此，我们可以在这个位置的状态转移方程中直接继承前一个状态的值并加1，即dp[i][j] = dp[i-1][j-1] + 1。

第二种情况：当两个字符串的当前字符不相等时（即s1[i] != s2[j]），这时需要考虑两种子情况：要么不选择第一个字符串的当前字符（即考察dp[i-1][j]），要么不选择第二个字符串的当前字符（即考察dp[i][j-1]）。

这两种情况中的最大值将成为当前状态的值，即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

值得注意的是，第三种可能性（即同时不选择两个字符）实际上已经被包含在上述两种情况中，因此不需要单独考虑。

所以dp[i][j] = max(dp[i - 1][ j ],dp[ i ][ j - 1])

3. 初始化：引入虚拟层（第0行和第0列）来简化边界条件的处理。具体来说，在原始字符串前添加一个虚拟的空字符，使得dp[0][j]和dp[i][0]都初始化为0，这表示空字符串与任何其他字符串的最长公共子序列长度自然为0

4. 填表顺序：填表顺序遵循自然的从左到右、从上到下的顺序，这样可以确保在计算每个状态时，其所依赖的子问题都已经被计算过。

5. 返回值：由状态表示可知dp[i][j]就表示第一个字符串[0,i]之间和第二个字符串[0,j]之间中的最长公共子序列的长度，所以直接返回dp[m][n]即可，其中 m 和 n 分别是两个输入字符串的长度。

class Solution {public int longestCommonSubsequence(String text1, String text2) {// 获取两个字符串的长度int m = text1.length(), n = text2.length();// 在原始字符串前添加一个空格，构造新的字符数组// 这样做的目的是:// 1. 保持索引映射关系更直观（从1开始）// 2. 空串（第0行/第0列）有实际意义，表示与空串的LCS长度为0char[] ch1 = (" " + text1).toCharArray(); char[] ch2 = (" " + text2).toCharArray();// 1. 创建dp表// dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度// 数组大小为(m+1)*(n+1)是为了包含空串的情况int[][] dp = new int[m+1][n+1];// 2. 初始化 - 有虚拟层(第0行和第0列)，所以不用显式初始化// dp[0][j]和dp[i][0]都默认为0，表示空串与任何字符串的LCS长度为0// 3. 根据状态转移方程进行填表for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {if(ch1[i] == ch2[j]) {// 如果当前字符相等，则LCS长度等于去掉这两个字符后的LCS长度加1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果当前字符不等，则LCS长度等于两个子问题的较大值：// 1. 去掉text1的当前字符// 2. 去掉text2的当前字符dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}// 4. 返回结果// dp[m][n]就是text1和text2的最长公共子序列长度return dp[m][n];}
}