最长递增子序列
动态规划解法
- 动态规划的核心设计思想是数学归纳法。
我们设计动态规划算法，不是需要一个 dp 数组吗？
我们可以假设 dp[0…i−1] 都已经被算出来了，然后问自己：怎么通过这些结果算出dp[i] ?
- 直接拿最长递增子序列这个问题举例你就明白了。
不过，首先要定义清楚 dp 数组的含义，即 dp[i] 的值到底代表着什么？
**我们定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。**<br /><br />**怎么设计算法逻辑来正确计算每个 dp[i] 呢？**
这就是动态规划的重头戏了，要思考如何进行状态转移，这里就可以使用数学归纳的思想：
状态转移方程
我们已经知道了 dp[0…4] 的所有结果，我们如何通过这些已知结果推出 dp[5] 呢？
- nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。
- 当然，可能形成很多种新的子序列，但我们只要最长的，把最长子序列的长度作为 dp[5] 的值即可。
base case
base case：dp 数组应全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1。完整代码：
- 至此，这道题就解决了，时间复杂度 O(N^2)。
首先明确 dp 数组所存数据的含义。
然后根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i−1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。
但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义； 或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。
二分查找解法
二分查找的细节
最长回文子序列
一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。
- 原因很简单，你想想一个字符串，它的子序列有多少种可能？起码是指数级的吧，这种情况下，不用动态规划技巧，还想怎么着呢？
- 既然要用动态规划，那就要定义 dp 数组，找状态转移关系。我们说的两种思路模板，就是 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。
思路1模板：一个一维的 dp 数组
- 上面的 【最长递增子序列】就是这么定义 dp数组：在子数组array[0..i]中，以array[i]结尾的目标子序列（最长递增子序列）的长度是dp[i]。
- 为啥最长递增子序列需要这种思路呢？前文说得很清楚了，因为这样符合归纳法，可以找到状态转移的关系，这里就不具体展开了。
思路2模板：一个二维的 dp 数组
- 这种思路运用相对更多一些，尤其是涉及 两个字符串/数组 的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。
2.1 涉及两个字符串/数组时（比如最长公共子序列）
dp 数组含义：在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]。
详解 最长回文子序列
dp 数组定义：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]。为了状态转移能归纳出思维
定义状态转移方程
具体来说，如果想求dp[i][j]，假设知道了子问题dp[i+1][j-1]的结果（s[i+1..j-1]中最长回文子序列的长度），你是否能想办法算出dp[i][j]的值（s[i..j]中，最长回文子序列的长度）呢？
- 可以！这取决于s[i]和s[j]的字符：
如果它俩相等，那么它俩加上s[i+1..j-1]中的最长回文子序列就是s[i..j]的最长回文子序列：
如果它俩不相等，说明它俩不可能同时出现在s[i..j]的最长回文子序列中，那么把它俩分别加入s[i+1..j-1]中，看看哪个子串产生的回文子序列更长即可：
以上两种情况：至此，状态转移方程就写出来了，根据 dp 数组的定义，我们要求的就是dp[0][n - 1]，也就是整个s的最长回文子序列的长度。
代码实现
- 首先明确一下 base case：如果只有一个字符，最长回文子序列长度是 1，也就是dp[i][j] = 1,(i == j)。
- 因为 i 肯定小于等于 j ，所以对于那些i > j的位置，根本不存在什么子序列，应该初始化为 0。
看看刚才写的状态转移方程，想求dp[i][j]需要知道dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]这三个位置；再看看我们确定的 base case，填入 dp 数组之后是这样：
<br />**为了保证每次计算dp[i][j]，左、下、左下三个方向的位置已经被计算出来，只能斜着遍历或者反着遍历**：<br /><br />我选择反着遍历，代码如下：<br /> 
总结
- 主要还是正确定义 dp 数组的含义，
- 子序列问题，首先想到两种动态规划思路，然后根据实际问题看哪种思路容易找到状态转移关系。
- 找到状态转移和 base case 之后，一定要观察 DP table，看看怎么遍历才能保证通过已计算出来的结果解决新的问题。
若有收获，就点个赞吧
0 人点赞
