4.2.4 实战 | 打印方案

记录转移路径，然后递归输出

动态规划打印方案的原则就是：记录转移路径，然后递归输出。它不记录每一步的具体方案，只记录“从哪来”。

用两个例子感受下。说明：一般情况，“子段/子串”是连续的一段，“子序列”可以不连续。

例 1：最长递增子序列

题目：最长递增子序列。给定一个整数数组 nums，找出最长严格递增子序列的长度。

分析问题

第一步，给重复子问题选代表。“代表”可以直接从题目中来，本实例就是“以 nums[i] 结尾的数组，最长严格递增子序列的长度是 opt[i]”，而这句话里就包含了状态 [i] 和最优化目标 opt[i]。bingo！

说明：“状态的定义”，可以从暴力搜索中提取（递归的参数+全局变量），也可以人力模拟求解过程进而提取变化的信息，也可以通过“轮廓的变化”来确定变化的信息（该例子就是，直接看重复子问题的变化趋势）。

第二步，确定状态转移方程，即最优化目标的递推公式。这就需要自己手动模拟下了。对于每个 [i] 它的最优化目标 opt[i] 的初始值都是 1（即它自己一个），再在它前面的数字 nums[j] 里，找到满足 nums[i] > nums[j] 的数（即严格递增），然后取 opt[j] + 1 里的最大值，就是 opt[i] 的值。

最优子结构 = 状态 + 最优化目标 + 递推公式

代码实现

动态规划的代码实现，如下：

var lengthOfLIS = function(nums) {
  const n = nums.length;
  // 最优化目标：以 nums[i] 结尾的最长严格递增子序列的长度是 opt[i]
  let opt = new Array(n).fill(1);
  // 动态规划：从小到大进行递推
  for (let i = 1; i < n; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (nums[i] > nums[j]) {
        opt[i] = Math.max(opt[i], opt[j] + 1);
      }
    }
  }
  return Math.max(...opt);
};

打印方案

记录 opt[i] 对应的最长严格递增子序列的末尾数字来源于谁——即它的前一个是谁，然后再沿着最大的 [max] 倒着找回去就可以了。

代码实现，如下：

var lengthOfLIS = function(nums) {
  const n = nums.length;
  let opt = new Array(n).fill(1);
  let pre = new Array(n).fill(-1); // 转移路径，初始值是-1（没有来源）
  for (let i = 1; i < n; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (nums[i] > nums[j] && opt[j] + 1 > opt[i]) {
        opt[i] = opt[j] + 1;
        pre[i] = j; // 从 j 来
      }
    }
  }
  // 找最大值的下标
  let ans = opt[0];
  let ansIndex = 0;
  for (let i = 1; i < n; i++) {
    if (opt[i] > ans) {
      ans = opt[i];
      ansIndex = i;
    }
  }
  // 递归输出：因为是倒序，所以在回溯时输出
  let ansList = [];
  const log = function(i) {
    if (pre[i] !== -1) log(pre[i]); // 若不是-1，则继续下探
    ansList.push(nums[i]); // 回溯时，再输出
  };
  log(ansIndex); // 从 ansIndex 开始递归输出
  console.log(ansList.join());

  return ans;
};

nums = [10,9,2,5,3,7,101,18] 会输出：2,3,7,101

打印逻辑的空间复杂度是 O(n)。

例 2：最长公共子序列

题目：最长公共子序列。给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。若不存在，就返回 0。

这个题目在上篇里已经详细讨论过了，这里就直接写打印方案的代码了。

打印方案

路径的来源有三种：对角线、左侧、正上方。代码实现如下：

var longestCommonSubsequence = function(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  let opt = new Array(m + 1);
  let pre = new Array(m + 1); // 转移路径的类型，1左侧，2正上方，3对角线
  for (let i = 0; i <= m; i++) {
    opt[i] = new Array(n + 1).fill(0);
    pre[i] = new Array(n + 1).fill(0); // 初始值是0
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        opt[i][j] = opt[i - 1][j - 1] + 1;
        pre[i][j] = 3; // 从对角线来
      } else {
        opt[i][j] = opt[i][j - 1];
        pre[i][j] = 1; // 从左侧来
        if (opt[i - 1][j] > opt[i][j]) {
          opt[i][j] = opt[i - 1][j];
          pre[i][j] = 2; // 从正上方来
        }
      }
    }
  }
  // 打印方案
  let ansList = [];
  const log = function(i, j) {
    const type = pre[i][j];
    if (type === 0 || opt[i][j] === 0) return; // 递归边界
    // 本层逻辑
    if (type === 1) log(i, j - 1);
    else if (type === 2) log(i - 1, j);
    else if (type === 3) {
      log(i - 1, j - 1);
      ansList.push(text1[i - 1]); // 当从对角线来时，再记录
    }
  };
  log(m, n); // 从 [m, n] 开始
  console.log(ansList.join(""));

  return opt[m][n];
};

text1 = "abcabcdbdxe", text2 = "xabcde" 会输出：abcde

打印逻辑的空间复杂度是 O(m*n)，存了转移类型一个值。

总结

这部分内容比较简单，就讨论了一件事，那就是：当要在动态规划里打印方案时，只要记录“转移路径”就可以了——它从哪来。

在具体应用时，有两个小点需要关注：一是转移路径如何记录（需要分析具体问题），二是因为是倒序记录的，所以递归输出的时机是在“回溯”时。