不相交的线

记住这套「相等取左上加一，不相等取上、左较大」，下面每填一格都在套它。

先搭表。行头是 nums1=[1,4,2]，列头是 nums2=[1,2,4]，最上一行和最左一列代表「一边为空」，连不出线，全部填 0（蓝色）。接下来从左上往右下一格格填内部。

填 [1,1] 这格：nums1 的 1 和 nums2 的 1 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。

左上角是 0，加上新连的这一条 = 1。这格落子 1（绿色）。

填 [1,2] 这格：nums1 的 1 和 nums2 的 2 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。

上面是 0，左边是 1，取较大 = 1。这格落子 1（绿色）。

填 [1,3] 这格：nums1 的 1 和 nums2 的 4 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。

上面是 0，左边是 1，取较大 = 1。这格落子 1（绿色）。

填 [2,1] 这格：nums1 的 4 和 nums2 的 1 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。

上面是 1，左边是 0，取较大 = 1。这格落子 1（绿色）。

填 [2,2] 这格：nums1 的 4 和 nums2 的 2 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。

上面是 1，左边是 1，取较大 = 1。这格落子 1（绿色）。

填 [2,3] 这格：nums1 的 4 和 nums2 的 4 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。

左上角是 1，加上新连的这一条 = 2。这格落子 2（绿色）。

填 [3,1] 这格：nums1 的 2 和 nums2 的 1 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。

上面是 1，左边是 0，取较大 = 1。这格落子 1（绿色）。

填 [3,2] 这格：nums1 的 2 和 nums2 的 2 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。

左上角是 1，加上新连的这一条 = 2。这格落子 2（绿色）。

填 [3,3] 这格：nums1 的 2 和 nums2 的 4 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。

上面是 2，左边是 2，取较大 = 2。这格落子 2（绿色）。

表填满了。右下角 dp[3][3] = 2，就是最多能连出的线数。

回看哪几步是「相等加一」：整张表其实有三格——[1,1] 连 1-1、[2,3] 连 4-4、[3,2] 连 2-2，都是踩着左上角加一长出来的。但 [2,3](4-4) 和 [3,2](2-2) 这两条会交叉，只能二选一；这条最优连线选了 [1,1] 和 [2,3] 两格（橙色），第三格 [3,2]（蓝色）连上就会和 4-4 撞，所以最多仍是 2 条。

边界先想清：全一致取满、有交叉要取舍、毫无公共值则为 0。

两个高频追问：认出它是 LCS、以及滚动数组压空间。