知识点
知识点
子序列问题
问题描述：
子序列问题很可能涉及到两个字符串，比如让你求两个字符串的 最长公共子序列
一般来说，这类问题都是让你求一个最长子序列，几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)
既然要用动态规划，那就要定义 dp 数组，找状态转移关系。一般子序列问题有两种dp数组
两种dp数组
一维dp数组：
例如最长递增子序列问题，dp 数组的定义是：在子数组array[0..i]中，以array[i]结尾的目标子序列（最长递增子序列）的长度是dp[i]。
二维dp数组
这种思路运用相对更多一些，尤其是涉及两个字符串/数组的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况：
涉及两个字符串/数组时（比如最长公共子序列、编辑距离）
dp 数组的含义如下：在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]。
只涉及一个字符串/数组时（比如最长回文子序列）
dp 数组的含义如下：在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]。
LeetCode算法
LeetCode算法
5.【最长回文子串】
解题思路：
1、动态规划解法：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。因此，利用数学归纳法，可以得出：判断从i到j的字符串是否为回文串，只需要i+1到j-1为回文串，并且Si==Sj即可，对应方程P(i,j)=P(i+1,j−1)∧(Si==Sj)。base case为，长度为1时必为回文，长度为2时判断两个字符即可。时间复杂度为O(n^2)，空间复杂度为O(n^2)
2、双指针解法：判断一个字符串是否为回文串，我们可以在其中间开始用双指针向左右遍历，因此，让i从0开始到s.length()-1，以s.charAt(i)为中心，从中间开始向两边扩散来判断回文串，不就可以找到s的所有回文子串了，只需调最长的即可。注意，回文串的长度可能是奇数也可能是偶数，因此我们需要考虑两种回文子串。时间复杂度O(n^2)，空间复杂度O(1)，该题目是少有的动态规划并非最佳答案的题。
516.【最长回文子序列】
解题思路：
使用动态规划做题。
首先，定义dp数组。我们使用二维dp数组，如何定义dp数组含义呢？找状态转移需要归纳思维，说白了就是如何从已知的结果推出未知的部分，因此，我们想求dp[i][j]，假设知道了子问题dp[i+1][j-1]的结果（s[i+1..j-1]中最长回文子序列的长度），如何通过已知的推出未知的？这取决于s[i]和s[j]的字符，如果相等，则说明最长回文子序列为s[i+1..j-1]中的最长回文子序列加上它俩；不相等，则说明最长回文子序列为s[i..j-1]或s[i+1..j]中最长回文子序列最长的。
其次，确定base case，如果只有一个字符，显然最长回文子序列长度是 1，也就是dp[i][j] = 1,(i == j)
最后，确定状态转移方程，状态转移方程在上一步中已经可以得到了。
如何遍历所有状态呢？dp[i][j]需要知道dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]这三个位置，为了保证每次计算dp[i][j]，左、下、左下三个方向的位置已经被计算出来，只能斜着遍历或者反着遍历。
01背包问题
解题思路：
经典的动态规划问题。
首先，确定状态和选择。状态有两个，物品和背包容量。选择，就是物品装入和不装入
其次，确定dp数组。dp数组就是对状态的描述，刚才找到的「状态」，有两个，也就是说我们需要一个二维dp数组，一维表示可选择的物品，一维表示背包的容量。然后定义dp数组，dp[i][w]的定义如下：对于i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。
然后，确定base case，base case就是当物品为0或者背包容量为0，则价值为0.
最后，确定状态转移方程。根据选择，列出状态转移方程，如果你没有把这第i个物品装入背包，最大价值dp[i][w]应该等于dp[i-1][w]，即继承之前的结果。如果你把这第i个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]
然后思考如何遍历状态即可。
京公网安备 11010502036488号