看了前文 动态规划解题套路框架，我知道了如何一步步优化动态规划问题；
看了前文前提概要，我知道了利用数学归纳法写出暴力解（状态转移方程）。
但就算我写出了暴力解，我很难判断这个解法是否存在重叠子问题，从而无法确定是否可以运用备忘录等方法去优化算法效率。
对于这个问题，其实我在动态规划系列的文章中写过几次，在这里再统一总结一下吧。
首先，最简单粗暴的方式就是画图，把递归树画出来，看看有没有重复的节点。
比如最简单的例子，动态规划解题套路框架 中斐波那契数列的递归树：
这棵递归树很明显存在重复的节点，所以我们可以通过备忘录避免冗余计算。
但毕竟斐波那契数列问题太简单了，实际的动态规划问题比较复杂，比如二维甚至三维的动态规划，当然也可以画递归树，但不免有些复杂。
比如在 最小路径和问题 中，我们写出了这样一个暴力解法：
int dp(int[][] grid, int i, int j) {
if (i == 0 && j == 0) {
return grid[0][0];
}
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
return Math.min(
dp(grid, i - 1, j),
dp(grid, i, j - 1)
) + grid[i][j];
}你不需要读过前文，光看这个函数代码就能看出来，该函数递归过程中参数 i, j 在不断变化，即「状态」是 (i, j) 的值，你是否可以判断这个解法是否存在重叠子问题呢？
假设输入的 i = 8, j = 7，二维状态的递归树如下图，显然出现了重叠子问题：
但稍加思考就可以知道，其实根本没必要画图，可以通过递归框架直接判断是否存在重叠子问题。
具体操作就是直接删掉代码细节，抽象出该解法的递归框架：
int dp(int[][] grid, int i, int j) {
dp(grid, i - 1, j), // #1
dp(grid, i, j - 1) // #2
}可以看到 i, j 的值在不断减小，那么我问你一个问题：如果我想从状态 (i, j) 转移到 (i-1, j-1)，有几种路径？
显然有两种路径，可以是 (i, j) -> #1 -> #2 或者 (i, j) -> #2 -> #1，不止一种，说明 (i-1, j-1) 会被多次计算，所以一定存在重叠子问题。
再举个稍微复杂的例子，后文 正则表达式问题 的暴力解代码：
bool dp(string& s, int i, string& p, int j) {
int m = s.size(), n = p.size();
if (j == n) return i == m;
if (i == m) {
if ((n - j) % 2 == 1) return false;
for (; j + 1 < n; j += 2) {
if (p[j + 1] != '*') return false;
}
return true;
}
if (s[i] == p[j] || p[j] == '.') {
if (j < n - 1 && p[j + 1] == '*') {
return dp(s, i, p, j + 2)
|| dp(s, i + 1, p, j);
} else {
return dp(s, i + 1, p, j + 1);
}
} else if (j < n - 1 && p[j + 1] == '*') {
return dp(s, i, p, j + 2);
}
return false;
}代码有些复杂对吧，如果画图的话有些麻烦，但我们不画图，直接忽略所有细节代码和条件分支，只抽象出递归框架：
bool dp(string& s, int i, string& p, int j) {
dp(s, i, p, j + 2); // #1
dp(s, i + 1, p, j); // #2
dp(s, i + 1, p, j + 1); // #3
}和上一题一样，这个解法的「状态」也是 (i, j) 的值，那么我继续问你问题：如果我想从状态 (i, j) 转移到 (i+2, j+2)，有几种路径？
显然，至少有两条路径：(i, j) -> #1 -> #2 -> #2 和 (i, j) -> #3 -> #3，这就说明这个解法存在巨量重叠子问题。
所以，不用画图就知道这个解法也存在重叠子问题，需要用备忘录技巧去优化。