1.解题方法：

1.1 递归

自顶向下开始暴力穷举每个计算结果。
优化：通过备忘录剪枝。

1.2 dp数组

自底向上构建dp数组，通过底层值根据状态转移方程构建出上层结果

2.题目类型

2.1 双字符串/数组问题：

求两个数组或者字符串的最长公共子序列问题，肯定是要用动态规划的。

• 首先，区分两个概念：子序列可以是不连续的；子数组（子字符串）需要是连续的；
• 另外，动态规划也是有套路的：单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

正确的思路是不要考虑整个字符串，而是细化到s1和s2的每个字符。对于两个字符串求子序列的问题，都是用两个指针i和j分别在两个字符串上移动，大概率是动态规划思路。
只需要对当前两个指针指向的字符进行判断和操作

1143. 最长公共子序列 (mid)

72. 编辑距离 (hard)

2.2 子序列问题：

2.2.1 单数组问题：

构建dp数组，然后根据数学归纳推到状态转移方程

300. 最长递增子序列 (mid)

构建dp数组
dp[i]代表对应的nums[i]最大递增个数

nums        10        9        2        5        3        7        101        18
index        0            1        2        3        4        5          6         7
dp            1            1        1        2        2        3          4         3

解释：

• dp[0] = 1 是因为nums[0]=10在第一位，index<i 没有比他更小的数字
• dp[1] = 1 是因为nums[1]=9在第二位，index<i 没有比他更小的数字
• dp[2] = 1 是因为nums[2]=2在第三位，index<i没有比他更小的数字
• dp[3] = 2 是因为nums[3]=5在第四位，index<i中，i=2时，nums[2]=2<5，所以在此位时，它的最大递增个数为dp[2]+1=1+1=2
• dp[4] = 2 是因为nums[4]=3在第五位，index<i中，i=2时，nums[2]=2<3，所以在此位时，它的最大递增个数为dp[2]+1=1+1=2
• dp[5] = 3 是因为nums[5]=7在第六位，index<i中，i=2时，nums[2]=2<7，所以在此位时，它的最大递增个数为dp[2]+1=1+1=2，i=3时，nums[3]=5<7，所以在此位时，它的最大递增个数为Math.max(dp[5],dp[3]+1=2+1=3)，i=4时，nums[4]=3<7，所以在此位时，它的最大递增个数为Math.max(dp[5],dp[4]+1=2+1=3)