题目链接
思路
分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律
在数组的动态规划问题中，一般 dp[i] 都是表示以 nums[i] 为结尾的状态；dp[i][j] 分别表示 以 nums1[i] 和 nums2[j] 为结尾的状态，以此类推
字符串也是个数组，是字符数组
表示状态
首先构思一下我们需要存储的信息，以此来确定 dp 数组的维数：
找状态转移方程
边界处理
空间优化
代码
dp数组版
空间优化版