都2024年了，还不会动态规划吗？我教你（三）

大家好呀，最近加班写作的时间有点少，还请见谅，（入职新公司三周，两个周末加班了三天）

本系列文章前面两篇

• 都2024年了，还不会动态规划吗？我教你🚀🚀🚀
• 都2024年了，还不会动态规划吗？我教你🚀🚀🚀（二）

前面两篇文章已经从递归到简单的动态规划，算是初窥门径，今天我们继续上强度，来学点更有挑战性的吧

最长递增子序列

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

例如：[6,3,1,5,2,3,7]，该数组最长上升子序列为 [1,2,3,7] ，长度为4

分析

我们先考虑边界情况，例如数组的长度为0，那么是最长递增子序列是数组的长度

然后找到我们的目标：找到最长的递增子序列长度，那么dp[i]标识当前数字对应的最长递增子序列长度，甚至可以猜测，dp[i] = dp[i-1] + 1

• 假设数组长度为1，[6]，那么最长递增子序列长度为1，
• 假设数组长度为2，[6, 3]，那么最长递增子序列长度为1，因为3<6
• 假设数组长度为3，[6, 3, 1]，那么最长递增子序列长度为1，因为我们已经知道，[6, 3]的递增子序列长度为1，而新增的数字1<3，所以最长递增子序列长度为1
• 假设数组长度为4，[6, 3, 1, 5]，那么最长递增子序列长度为2，因为我们已经知道，[6, 3, 1]的递增子序列长度为1，而新增的数字5>3，5>1，分别构成了两个长度为2的递增子序列，所以最长递增子序列长度更新为2。-假设数组长度为5，[6, 3, 1, 5, 2]，2<6 2<3 2>1 2<5，构成了一个递增子序列，长度为2，那么最长递增子序列依然为2，
• 假设数组长度为6，[6, 3, 1, 5, 2, 3]，3<6 3=3 3>1 3<5 3>2，构成一个递增子序列[1, 2, 3] 那么最长递增子序列更新为3，
• 假设数组长度为7，[6, 3, 1, 5, 2, 3, 7]，7>6、7>3、7>1、7>5、7>2，7>3，g构成多个递增子序列，其中[1, 2, 3, 7]最长，长度为4，那么最长递增子序列长度更新为4

通过上面的推断过程，我们可以发现几个特点：

• 每次新增一个长度，都要拿新增的数从头和每一位比较大小，很明显这是个双循环结构
• 当新增的数比前面的数大时，可以构成递增序列
• 但是遇到类似7>3、7>1时，无法构成长度大于2的子序列，区分这种情况的依据是，使用上次的dp[i - 1]和当前的dp[i]比较：dp[i] < dp[i-1] + 1
• 我们还需要额外维护一个变量记录最大值，每次有更长的递增子序列长度时，更新这个最大值，max = Math.max(max, dp[i])

下面是实现

export function LIS(arr: number[]): number {
    // write code here
    if (!arr.length) return arr.length;
    const dp = new Array(arr.length).fill(1);

    let max = 1;
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                 max = Math.max(max, dp[i]);
            }
        }
    }
    return max;
}

可能有的同学会好奇，为啥会在if中&& dp[i] < dp[j] + 1，这是因为符合(arr[i] > arr[j]的情况很多，但是并没有影响最长子增子序列长度的最大值。

还有个技巧，为了节约空间，每个子循环（j的循环）并没有创建新的dp数组，而是使用全局的dp数组，这样做还有个好处，dp数组用于记录以每个元素结尾的最长递增子序列的长度，在外层循环中不断更新和累积这些历史信息，保证每次计算dp[i]时都能利用之前计算的结果。这也是状态转移方程的精髓。

现在我们可以在增加强度，需要输出最长递增子序列

这类问题常常伴随着动态规划问题一起出现，需要借助回溯算法实现。这里不做回溯算法的延伸了，现在只需要知道，我们需要记录每次最大长度改变时，同时记录对应的下标（前驱），以便在后面的回朔时作为依据。

另外还要记录最终最大值时的下标，作为回朔的起点。

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  const prev = new Array(n).fill(-1); // 记录前驱

  let maxLen = 1;
  let maxIndex = 0;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
        prev[i] = j; // 记录前驱
      }
    }
    if (dp[i] > maxLen) {
      maxLen = dp[i];
      maxIndex = i;
    }
  }

  // 回溯找到 LIS
  const lis: number[] = [];
  let index = maxIndex;
  while (index !== -1) {
    lis.unshift(nums[index]);
    index = prev[index];
  }

  return lis;
}

最后

鉴于文章过长，关于 Vue diff算法的核心，下篇文章我将详细阐述