一张表，八句话看懂动态规划(DP)思路 (以Leetcode 718.最长重复子数组为例的讲解)

题目描述

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray

正文

找两个数组的“公共”部分，实际上就是两个数组相同的数字。
我把这些公共的地方，在这张表格里用1来表示：

那么什么是“连续”的公共部分呢？其实就是在刚才我们标1的位置，找到一条或多条能从【左上】连到【右下】的线。
注意，一定要是【左上】连到【右下】，如下图表示。

那么，如何在动态更新中，记录每一条线的长度呢？
答案是：每次先看一眼当前格子是否A、B对应位置的数字相等，
然后看一下【左上】角的数字，将其+1，写在当前位置即可（如果左上角是空白，则说明左上角数字=0）。动态过程如下：





找到整张表格里最大的数字，就是我们能找到的最长路线长度了。