【记忆化搜索】最长递增子序列

文章目录 300. 最长递增子序列解题思路：递归 -> 记忆化搜索

300. 最长递增子序列

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

提示：

1 <= nums.length <= 2500-104 <= nums[i] <= 104

进阶：

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

---

解题思路：递归 -> 记忆化搜索

​ 如果我们要直接递归进去求整个数组的最长递增子序列的长度的话，其实不好搞，但是如果我们在主函数中用一个 for 循环，遍历每个元素，让每个元素都作为起点获取其最长递增子序列的长度，然后再记录下最长的那个就行了，这样子相对来说好办一些！

​ 也就是说递归函数 dfs() 需要传入一个当前元素的起点 pos，然后负责帮我们拿到以该 pos 为起点的最长递增子序列的长度，所以它的返回值类型是 int。

​ 至于递归函数体，其实也是一个循环，因为我们在主函数中以某个元素为起点进行递归之后，其实到了下一层中就是找到符合递增的元素，然后继续递归求其最长子序列长度，以此类推，我们只需要关注一层的细节即可！如下图简单所示：

class Solution { public: int lengthOfLIS(vector<int>& nums) { int ret = 0; for(int i = 0; i < nums.size(); ++i) ret = max(dfs(nums, i), ret); // 获取以i元素开头得到的最长子序列，然后记录最长的那个 return ret; } int dfs(vector<int>& nums, int pos) { int ret = 1; for(int i = pos + 1; i < nums.size(); ++i) { // 遍历pos后面的所有位置，看看谁能加到pos这个元素的后面 if(nums[pos] < nums[i]) ret = max(ret, dfs(nums, i) + 1); } return ret; } };

​ 这种写法毋庸置疑，是会超时的，因为从上面的递归树就能看出，虽然没画全，但是可以想象出其中是有很多重复的子树的，所以我们可以用记忆化搜索了解决问题，就是添加一个备忘录，具体步骤这里不再赘述，直接上代码：

class Solution { private: int memory[2501] = { 0 }; // 一维数组作为备忘录，初始化为0即可 public: int lengthOfLIS(vector<int>& nums) { int ret = 0; for(int i = 0; i < nums.size(); ++i) ret = max(dfs(nums, i), ret); // 获取以i元素开头得到的最长子序列，然后记录最长的那个 return ret; } int dfs(vector<int>& nums, int pos) { // 在进入函数之前，判断是否已经存在过备忘录中了 if(memory[pos] != 0) return memory[pos]; int ret = 1; for(int i = pos + 1; i < nums.size(); ++i) { // 遍历pos后面的所有位置，看看谁能加到pos这个元素的后面 if(nums[pos] < nums[i]) ret = max(ret, dfs(nums, i) + 1); } // 离开函数之前，将当前结果计入备忘录 memory[pos] = ret; return ret; } };

​ 可以看到，代码中只改动了三处地方：创建备忘录、添加结果到备忘录、检查备忘录！瞬间就跑通了，还干掉了 80% 的解法！