300. Longest Increasing Subsequence

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  // 获取数组长度，处理边界情况：空数组直接返回0
  const n = nums.length
  if (n === 0) return 0

  // 初始化记忆化缓存数组，用于存储已经计算过的dfs(i)结果，避免重复计算
  // 初始值为-1，表示该位置尚未计算
  const memo = new Array(n).fill(-1)

  /**
   * 深度优先搜索函数：计算以nums[i]为结尾的最长递增子序列长度
   * @param {number} i - 当前元素的索引
   * @return {number} - 以nums[i]结尾的最长递增子序列长度
   */
  const dfs = (i) => {
    // 如果当前索引的结果已经计算过，直接返回缓存值（记忆化核心）
    if (memo[i] !== -1) return memo[i]

    // 初始化结果为0：表示初始状态下，没有比nums[i]小的前驱元素
    let res = 0

    // 遍历i之前的所有元素（j < i），寻找可以作为nums[i]前驱的元素
    for (let j = 0; j < i; j++) {
      // 如果nums[j] < nums[i]，说明nums[j]可以作为nums[i]的前驱
      if (nums[j] < nums[i]) {
        // 递归计算以nums[j]为结尾的最长递增子序列长度，并更新res为最大值
        res = Math.max(res, dfs(j))
      }
    }

    // 最终结果：找到的最长前驱子序列长度 + 1（加上当前元素nums[i]本身）
    // 并将结果存入缓存，供后续复用
    memo[i] = res + 1
    return memo[i]
  }

  // 遍历数组中每个元素作为子序列结尾，计算所有dfs(i)的最大值，即为整个数组的LIS长度
  let maxLength = 0
  for (let i = 0; i < n; i++) {
    maxLength = Math.max(maxLength, dfs(i))
  }

  return maxLength
}

问：什么样的题目适合「选或不选」，什么样的题目适合「枚举选哪个」？

答：我分成两类问题：

相邻无关子序列问题（比如 0-1 背包），适合「选或不选」。每个元素互相独立，只需依次考虑每个元素选或不选。 相邻相关子序列问题（比如本题），适合「枚举选哪个」。我们需要知道子序列中的相邻两个数的关系。对于本题来说，枚举 nums[i] 必选，然后枚举前一个必选的数，方便比大小。如果硬要用「选或不选」，需要额外记录上一个选的数的下标，算法总体的空间复杂度为 O(n2)，而枚举选哪个只需要 O(n) 的空间。

如果是相邻相关问题，用“以 i 结尾”或者“以 i 开头”思考；如果是相邻无关问题，用前缀或者后者思考，比如在 [0,i] 中选一个数，等于 j 的方案数。

相邻相关和相邻无关

相邻相关 & 相邻无关 核心解释

这两个概念是针对子序列 / 子集类动态规划问题的划分，核心区别在于：题目对选出的子序列中「元素间的相邻逻辑关系」是否有明确约束 / 依赖，简单说就是选出来的元素彼此之间要不要满足某种相邻的规则 / 比较关系。

一、相邻无关（子序列元素无依赖）

核心特征

选出的子序列中，元素之间不需要满足任何相邻的逻辑关系，每个元素的选择是独立的，仅需考虑「选这个元素」或「不选这个元素」对结果的影响，最终结果只和「选了哪些元素」有关，和「元素间的相对顺序 / 大小 / 关联」无关。

典型例子

• 0-1 背包问题：选物品时只考虑重量和价值，选 A 物品和选 B 物品之间没有任何依赖（不需要 A 和 B 满足大小、顺序等关系），仅需依次判断每个物品「选 / 不选」。
• 子集和问题：判断是否能选出子集和为 target，元素间无任何约束，仅需独立考虑每个元素的选 / 不选。

解题思路：选或不选

对每个元素依次做决策：

• 不选：当前结果继承前一个元素的决策结果；

• 选：在满足题目基础条件的前提下，更新当前结果。

  无需记录上一个选的元素是什么，因为元素间无依赖。

二、相邻相关（子序列元素有依赖）

核心特征

选出的子序列中，相邻元素之间必须满足某种明确的逻辑约束（比如本题的严格递增、最长递减子序列的严格递减、最长公共子序列的顺序匹配等），后一个元素的选择依赖于前一个选的元素，必须通过前一个元素的状态来判断当前元素是否能选。

典型例子

• 本题：最长严格递增子序列（LIS）：要求子序列严格递增，因此选第i个元素作为子序列末尾时，必须知道前一个选的是哪个元素，并判断前一个元素的值是否小于nums[i]。
• 最长公共子序列（LCS）：要求子序列元素在原数组中顺序一致，因此当前元素的选择依赖于两个数组前一个位置的匹配状态。

解题思路：枚举选哪个

通常固定最后一个选的元素（比如本题固定nums[i]为子序列末尾），然后向前枚举所有可能的前一个元素（nums[j], j < i），判断是否满足相邻约束（nums[j] < nums[i]），再基于前一个元素的状态更新当前状态。

这种思路只需记录「以每个元素为末尾的最优解」，空间复杂度更低。

dfs(i) 的核心定义

dfs(i) 表示：以数组中第 i 个元素（也就是 nums[i]）作为「最后一个元素」的最长递增子序列的长度。