DP 进阶与回溯模板

// 运行环境：Node.js 14+
// 保存为 dsa-l21.js，执行：node dsa-l21.js

// 最长递增子序列 LIS：dp[i]=以 i 结尾的 LIS 长度
function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1)
  let max = 1
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++)
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1)
    max = Math.max(max, dp[i])
  }
  return max
}

// 最长公共子序列 LCS（二维 DP）
function longestCommonSubsequence(a, b) {
  const m = a.length, n = b.length
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i-1] === b[j-1] ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1])
  return dp[m][n]
}

// 回溯模板：选择 → 递归 → 撤销
function permutations(nums) {
  const res = [], path = [], used = new Array(nums.length).fill(false)
  const backtrack = () => {
    if (path.length === nums.length) { res.push([...path]); return }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue
      used[i] = true; path.push(nums[i])  // 选择
      backtrack()                          // 递归
      path.pop(); used[i] = false          // 撤销
    }
  }
  backtrack()
  return res
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) // 4 ([2,3,7,101])
console.log(longestCommonSubsequence('abcde', 'ace'))   // 3
console.log(permutations([1, 2, 3]).length)            // 6