如何将Top Down递归DP转为Bottom Up迭代DP及LIS问题优化

一、Top Down转Bottom Up的通用步骤 #

• 明确状态定义：先搞清楚递归DP中每个状态的具体含义，比如你原代码里dp[index][prev]代表从第index个元素开始，前一个选取的数值为prev时，能得到的最长严格递增子序列长度。
• 确定初始状态：对应递归的终止条件，比如原问题中当index == N时返回0，那么Bottom Up里要先初始化所有dp[N][*] = 0。
• 确定遍历顺序：递归是从起始状态向终止状态推进，Bottom Up则要反向遍历，从终止状态往起始状态填充dp数组。比如原问题中index从0到N，那Bottom Up就从index = N-1倒着遍历到0。
• 平移状态转移方程：把递归里的状态转移逻辑直接改成迭代形式，填充dp数组的对应位置。
• 定位最终答案：找到对应起始状态的dp值，比如原问题里就是dp[0][初始prev值]。

二、你的Top Down解法超时原因 #

你的代码中dp的第二维依赖于nums的数值范围，如果nums里存在极大值（比如1e9），dp数组会变得异常庞大，不仅内存占用爆炸，数组的初始化和访问操作也会耗费大量时间，直接导致超时。

三、LIS问题的Bottom Up优化解法 #

优化状态定义，不再用数值作为dp的第二维，而是用dp[i]表示以第i个元素结尾的最长严格递增子序列长度。这种方式空间复杂度降至O(n)，时间复杂度为O(n²)，能解决大部分常规测试用例的超时问题：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [1] * n
        max_len = 1
        # 遍历每个元素，计算以它结尾的最长递增子序列长度
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            max_len = max(max_len, dp[i])
        return max_len

四、更优的O(n log n)解法 #

如果nums的长度极大（比如1e5），O(n²)的解法仍会超时，此时可以采用贪心+二分查找的组合方法：
维护一个tails数组，其中tails[i]代表长度为i+1的最长递增子序列的最小结尾元素。遍历每个num时，用二分查找找到第一个大于等于num的位置并替换它；若num比tails中所有元素都大，则追加到末尾。最终tails的长度就是最长递增子序列的长度：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for num in nums:
            left, right = 0, len(tails)
            # 二分查找第一个>=num的位置
            while left < right:
                mid = (left + right) // 2
                if tails[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            if left == len(tails):
                tails.append(num)
            else:
                tails[left] = num
        return len(tails)

内容的提问来源于stack exchange，提问作者Bluebeard