算法：从暴力递归到动态规划

前言

本文通过介绍一道LeetCode算法题的三种解法(Java代码实现)，分析各解法的复杂度及优缺点，探索它们的内在逻辑联系，分享一种算法优化思路。

题目

LeetCode 139题：单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请判断是否可以利用字典中出现的单词拼接出 s 。
注意：
不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
案例：
输入：s = “leetcode”, wordDict = [“leet”, “code”]
输出：true

解法1 - 暴力递归

首先，理解题目的意思，就是要将字符串 s 拆分为多个子串，使得每个子串都在字典 wordDict 出现。最简单的思路就是穷举所有的拆分可能性，如果存在一种满足题意，那么有解，否则无解。我们可以枚举第一个子串，如果第一个子串在字典中出现，那么只需要判断剩余部分能否拆分，显然这是一个规模更小的子问题，可以直接用递归实现。代码如下：

public boolean wordBreak(String s, Set<String> wordSet) {
    if ("".equals(s)) return true;
    //枚举第一个子串
    for (int i = 1; i <= s.length(); i++) {
        //若这个子串在字典中出现，则将原串剩余部分递归
        if (wordSet.contains(s.substring(0, i))) {
            if (wordBreak(s.substring(i), wordSet)) return true;
        }
    }
    return false;
}

代码很简单，对程序员友好，但对电脑可能不太友好，为什么？我们分析下时间复杂度。设 s 的长度为 n ，每层函数有一个 for 循环，第一层长度为 n ，第二层长度最长可达 n - 1 ，第三层函数长度最长可达 n - 2，… ，相乘为 n! ，故时间复杂度为 O(n!) ，n 值稍微大一点，计算量就是天文数字，另外，还可能因为递归过深导致栈溢出。

解法2 - 记忆搜索

仔细分析上述的求解过程，可以发现递归过程其实存在很多重复计算。比如 s = “aaxxxxx” ，拆出 “a” ，“a”，求 “xxxxx” 是否可拆，拆出 “aa” ，求 “xxxxx” 是否可拆，多次求解 “xxxxx” 必定得到相同的结果，很显然这种重复计算是没有必要的，那么很自然可以想到，同类问题只求一次，然后把答案缓存起来，下次同类问题直接查缓存，就可以避免重复计算了。代码如下：

public boolean wordBreak(String s, Set<String> wordSet) {
    Map<Integer, Boolean> map = new HashMap<>();
    return wordBreak(s, 0, map, wordSet);
}

private boolean wordBreak(String s, int begin, Map<Integer, Boolean> map, Set<String> wordSet) {
    if (begin == s.length()) return true;
    //枚举第一个子串
    for (int i = begin + 1; i <= s.length(); i++) {
        //若能匹配单词
        if (wordSet.contains(s.substring(begin, i))) {
            //查哈希表看能否直接得到结果，查不到则递归求解
            Boolean flag = map.get(i);
            if (flag == null) {
                flag = wordBreak(s, i, map, wordSet);
                map.put(i, flag);
            }
            if (flag) return true;
        }
    }
    return false;
}

通过上述改进，我们保证了每个子问题只被求解一次，由于每次都是拆出第一个子串，将剩余部分递归，剩余部分是一个从原串的任意位置起到其末尾位置的子串，一共有 n 种可能，故子问题的个数为 n ，所以最多递归 n 次，开辟 n 个函数，每个函数有一层 for 循环，长度最大为 n ，所以时间复杂度为 O(n^2) ，相比于 O(n!) 得到了质的飞跃，但是由于沿用递归，在递归深度过大时，仍然存在栈溢出的可能。

解法3 - 动态规划

进一步分析上述解法，可以发现一个现象，每次求解一个问题，总是要先求规模更小的子问题，子问题又依赖规模更小的子问题，缓存表中最先出现最小问题的解，然后出现较小问题的解，然后出现较大问题的解，最后出现原问题的解，并且每个问题的解都依赖于所有比这个问题更小的子问题的解。
设字符串 s 的长度为 n ，问题抽象为函数 f(n) ，n = 5 ，那么求 f(5) 必先求 f(4)、f(3)、(2)、f(1) ，求 f(4) 必先求 f(3)、(2)、f(1) ，… ，反过来说，知道 f(1) ，可以推出 f(2) ，知道 f(2)、f(1) ，可以推出 f(3) ，知道 f(3)、(2)、f(1) ，可以推出 f(4) ，知道 f(4)、f(3)、(2)、f(1) ，可以推出 f(5) 。
基于上述分析，我们可以将递归过程转为递推过程，形成标准的动态规划解。代码如下：

public boolean wordBreak(String s, Set<String> wordSet) {
    //dp[i]表示s[i...n-1]能否拆分
    boolean[] dp = new boolean[s.length() + 1];
    dp[s.length()] = true;
    //i为子串起点
    for (int i = s.length() - 1; i >= 0; i--) {
        //j为子串终点，j+1为剩余串起点
        for (int j = i; j < s.length(); j++) {
            //若s[i...j]能在字典找到，判断s[j+1...n-1]能否拆分
            if (wordSet.contains(s.substring(i, j + 1))) {
                if (dp[j + 1]) {
                    dp[i] = true;
                    break;
                }
            }
        }
    }
    return dp[0];
}

函数内两层 for 循环，每层最大长度为 n ，故时间复杂度为 O(n^2) ，与解法2一致，所以本质上，记忆搜索与动态规划两种解法等价，但是动态规划避免了递归，所以解决了栈溢出的问题。至此，我们得到一个较为理想的解法，时间复杂度合理，没有栈溢出风险。这里我省略了空间复杂度的分析，主要是因为三种解法空间复杂度一致，都是 O(n) 。