算法细节系列（11）：再谈动态规划

用户1147447

发布于 2019-05-26 10:00:35

7640

发布于 2019-05-26 10:00:35

再谈动态规划

之前有一篇博文专门讲了什么是动态规划，但发现哪怕是理解了什么是动态规划，在实际刷题时也遇到了很多麻烦。究其原因，对动规的理解还不够透彻，其次对状态的递归和迭代的转化不够熟练，所以遇到一个问题时，无法立刻写出递推式。本篇重在讨论如何利用递归技术实现记忆化搜索，在此基础上呈现问题从递归到迭代的转换，即动态规划。

139 Word Break

以下题目摘自leetcode的Word Break系列，简单来说，就是让字典里的单词组成一个字符串，或者说检查字符串是否划分成字典里的多个单词，来看道题。

Problem：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given s = “leetcode”, dict = “leet”, “code”. Return true because “leetcode” can be segmented as “leet code”.

递归方案

最navie的想法，就是让dict中的单词去匹配字符串，所以我们可以很容易想到一种递归，如找到leet，那么再拿剩下的code去dict中找，如果找到就返回true。

所以一种简单的递归结构是：

1. 从字符串s中找出一个dict，如果dict在中间，则划分成左半部分和右半部分。
2. 分别对左半部分和右半部分做相同的递归操作。
3. 直到字符串为空，则返回true

这是我的思路，但里面存在很多问题，如为什么找出的dict会在s的中间，能否规避这种情况？其次，这种解法本身符合所有测试用例么？

我们看一个测试用例：

s="abcdeefg" dict=["ab","cde","ee","cd","fg"]

加入我们选取了字典中的cde，那么所导致的分割为ab和efg，而在这种情况下，子问题将返回false，所以上述思路是明显不能适应所有情况。

我们最初的想法是从字典中找寻单词去匹配字符串，但其实我们可以反过来思考，假设待匹配的字符串能由字典组成了，那么我们就可以从字符串头开始寻找对应的单词。如s = "abcdeefg",遍历字典，总能找到ab，这样我们可以把字符串划分为子字符串cdeefg进行递归查找。

这种方法就能很好的支持字符串中出现多个字典匹配的情况，如处理cdeefg的匹配问题时，我们实际可以找到cd和cde两种模式，而对应的子子问题分别是eefg和efg，这种方案就能遍历字典集，而不会出现漏检的情况。所以像这样的问题，递归中一定含有多个子递归。代码如下：

    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreak(s, wordDict);
    }

    private boolean wordBreak(String s, List<String> wordDict) {

        if (s.length() == 0) return true;

        //针对每一种可能的划分情况
        for (int i = 1; i <= s.length(); i++){
            String ss = s.substring(0, i);
            if (wordDict.contains(ss) && wordBreak(s.substring(i,s.length()),wordDict,mem)){
                return true;

            }
        }
        return false;
    }

这是一种解决方案，遍历对象为我们的字符串。当然，我们也可以以字典为遍历对象，从字典中找寻符合的字符串进行划分，可以写成如下：

for (String ss : wordDict){
    if (s.startsWith(ss) && wordBreak(s.substring(ss.length()), wordDict, mem)) return true;
}

但不管是哪种方案，你会发现在递归中出现了多个子问题，遇到多个子问题，咱们就可以考虑是否能用记忆化手段解决。原因很简单，多个子问题中，在递归时有可能会出现重复子问题。所以上述代码会TLE！

记忆方法代码如下：

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> mem = new HashSet<>();
        return wordBreak(s, wordDict,mem);
    }

    private boolean wordBreak(String s, List<String> wordDict, Set<String> mem) {

        if (s.length() == 0) return true;

        if (mem.contains(s)) return false;
        mem.add(s);

        //针对每一种可能的划分情况
        for (int i = 1; i <= s.length(); i++){
            String ss = s.substring(0, i);
            if (wordDict.contains(ss) && wordBreak(s.substring(i,s.length()),wordDict,mem)){
                return true;
            }
        }
        return false;
    }

它的记忆化非常巧妙，观察代码你会发现，主要是为了规避相同的子问题求解，减少递归，而在if语句中，我们的第一守卫是wordDict.contains(ss)，他负责把不需要的情况排除，但是它没有做到一点，如：

s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
dict = ["a","aa","aaa","aaaa","aaaaa","aaaaaa"]

不管该答案最后能不能被划分，刚进入递归，符合第一守卫的条件为：

1. a
2. aa
3. aaa
4. aaaa
5. aaaaa
6. aaaaaa

这六种情况，都会形成六个子问题继续递归，就拿第一种情况来说，它下一子问题的递归数量还是6种情况，因为守卫条件单纯的只是拿字典中的单词匹配，所以它的最坏情况就是O(6n)O(6^n)，n是字符串s的长度。那么一个简单的想法就是记录所有匹配成功的情况，让这些成功匹配的字符串“加入”字典中，但发现它实际很难操作，因为它是自顶向下去搜索答案的，在搜索的过程中，我们并不知道哪条路径上的字符串是匹配成功的，直到遍历结束返回时我们才能拿到匹配成功的字符串。

所以本题的记忆化很奇特，返回的是false，我刚开始一直不明白咋记录了错误的结果！其实它所记录的都是还未匹配的字符串。如初始条件，记录的就是最原始的字符串，它还未匹配。简单说说它为什么能work，再举个简单点的例子：（后来发现，它还是最单纯的记忆手段，记录状态和函数返回值）

s = "aaaaa"
dict = ["a","aa","aaa"]

第一次递归，会出现三种可能的子问题，未匹配字符串为

递归层数 1        递归层数 2
匹配   未匹配     匹配    未匹配
a      aaaa     a       aaa
aa     aaa      ...     ...
aaa    aa       ...     ...

你要一一举出的话，在递归层数2中有9种情况，我们可以看看递归层数1中和递归层数2中，在未匹配字符串上出现了子问题，所以早在不断遍历a的过程当中，就记录了一次aaa未匹配的值，而当从aa发展子问题时，就可以直接返回false，因为我们在a的递归问题中做过该问题了，如果a中有路径发展成true，那么自然不会遗留给aa去做，所以aa关于未匹配的aaa没必要去搜索了。

说了那么多，总结一下，该问题可以用递归+记忆化的手段去做，但做递归时，我们可以利用路径搜索的有序性，把每层的【未匹配字符串】记录下来，所利用的依据就是说，【同样的字典集】，某个递归发展的子问题你解决不了，那么以其他递归发展下来的相同子问题，你也解决不了。

动态规划

有了递归记忆搜索的解决方案，我们再来看看动规是如何解决该问题的，很有趣，它们互为逆向过程，刚才递归的尴尬在于无法在搜索路径上确定哪些答案是正确的，这难道是动规引出的后效性原理？哈哈，还不理解。现在做到的递归多数是不到最后一刻不知道结果的尴尬情景，那么动规能解决什么问题？

新的认识：自底向上的构建结果，在构建过程中，有能力把中间状态记录下来，而自底是关键，你也能从代码上看出很大的区别，递归方案的循环较少，而动规的循环却如此吓人，因为动规从底构建解啊，它并不知道到底那个方案是正确的，所以刚开始一定得把每种状态考虑进去。此时，我们再来看看动规的解决方案，就有了一种新的认识，千万别拿代码去验证答案，对解决问题绝对无用！

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] f = new boolean[s.length()+1];

        f[0] = true;

        for (int i = 1; i <= s.length(); i++){
            for (int j = 0; j < i; j++){
                if(f[j] && wordDict.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }

        return f[s.length()];
    }

好了，现在我们从动规的结构去认识该问题，动规需要明确三点：

状态是什么？
状态和状态之间如何转换？
状态的构建顺序如何？

就从递归的解决方案来看，它的状态就是待匹配的字符串true or false，所以可行的方案就是map.put(s,canForm ? true: false)，但需要使用map么？字符串匹配的状态可以由当前字符串的长度唯一记录。这种信息的约简很神奇，有悖于人类思维。比如说：s= "leetcode","leecode"，我们给了dict = {"leet","code"}，很明显leetcode能够成功匹配，而我们做匹配时，始终把leet放在了眼里，但一旦匹配成功，我们需要l,e,e,t的信息么？关键问题就在于某个问题一旦被你解决，它的冗余信息就可以被去除，这是动规难以理解的原因之一，状态的值很容易求解，但如果确保状态和值之间是唯一对应就成了难点。上述问题，我们可以用位置去代表状态和值之间的关系，所以有了连续字符串长度来代表状态值。

boolean[] f = new boolean[s.length()+1]

注意它的连续性，它深刻的决定了遍历的顺序。好了，状态明确了，现在再来看看代码，似乎就能理解它的深刻含义了，首先循环结构：

for (int i = 1; i <= s.length(); i++){
            for (int j = 0; j < i; j++){
                // ......
            }
}

因为我们不知道到底哪种prefix最终形成解，所以得把所有情况给遍历一次，也就有了两层循环的结构。

遍历顺序一定是prefix遍历（假设待匹配字符串是正确的搜索方案），状态如何改变呢？subString(j,i)也很有特点，除了遍历所有可能的prefix以外，还需要遍历postfix，为的就是在最底层把所有情况都考虑进来，乍一看该循环特别吓人，但别忘了守卫条件，首先不管是前缀后缀，都必须出现在字典集中，其次哪怕后缀匹配成功，也得保证后缀的前缀必须已经匹配成功，否则不去更新！所以可以想象，这种暴力的做法虽然看着非常吓人，但一大部分遍历是被屏蔽的。

总结：

思考问题的角度：假设待匹配的字符串正确，寻求正确匹配的解决方案，而不是寻求非正确匹配的解决方案。
理解动规的循环关键在于得把所有可能的状态考虑进来，它们未必能构成正确解，但确是正确解路径上不可或缺的一部分。
状态变量的约简，去除冗余信息，这得具体问题具体分析，需要有敏锐的观察力，深邃的思考和丰富的经验，快不得。

140. Word Break II

Problem:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words. Return all such possible sentences. For example, given s = “catsanddog”, dict = “cat”, “cats”, “and”, “sand”, “dog”. A solution is “cats and dog”, “cat sand dog”.

吼吼，这道题是状态记录的升级版，现在要求把所有可能的路径给求出来。

public List<String> wordBreak(String s, List<String> wordDict) {
        return canForm(s, wordDict, new HashMap<>());
    }

    private List<String> canForm(String s, List<String> wordDict, Map<String, List<String>> map){

        if (map.containsKey(s)) return map.get(s);

        List<String> ans = new ArrayList<>();
        if (s.length() == 0){
            ans.add("");
            return ans;
        }

        for (String word : wordDict){
            if (s.startsWith(word)){

                List<String> subList = canForm(s.substring(word.length()), wordDict, map);
                for (String sub : subList){
                    ans.add(word + (sub.isEmpty() ? "" : " ") + sub);
                }
            }   
        }
        map.put(s, ans);
        return ans;
    }

理解了word break ，这道题也就不难理解，原先我们递归结束时，返回true，并且让true一层层向上传递。而此时，递归能结束（说明匹配一定成功），那么递归返回时，把所有结果记录在list中即可。此时，返回的结果不是单纯的true or false，所以用map来存放键值对。

472. Concatenated Words

Problem:

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:

Input: “cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat” Output: “catsdogcats”,”dogcatsdog”,”ratcatdogcat” Explanation: “catsdogcats” can be concatenated by “cats”, “dog” and “cats”;undefined “dogcatsdog” can be concatenated by “dog”, “cats” and “dog”;undefined “ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.

Note:

The number of elements of the given array will not exceed 10,000
The length sum of elements in the given array will not exceed 600,000.
All the input string will only include lower case letters.
The returned elements order does not matter.

一个道理，输入中混杂了字典和匹配单词，所以直接从输入中筛选即可，筛选规则就是word break中的方法，如果能够匹配，就加入到list中。

public List<String> findAllConcatenatedWordsInADict(String[] words) {

        List<String> ans = new ArrayList<>();
        Set<String>  set = new HashSet<>();

        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });

        for (int i = 0; i < words.length;i++){
            if(wordBreak(words[i],set)){
                ans.add(words[i]);
            }
            set.add(words[i]);
        }

        return ans;
    }

    //139. Word Break
    private boolean wordBreak(String s, Set<String> wordDict){

        if(wordDict.isEmpty()) return false;

        boolean[] f = new boolean[s.length() + 1];

        f[0] = true;

        for (int i = 1; i <= s.length(); i++){
            for (int j = 0; j < i; j++){
                if (f[j] && wordDict.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[s.length()];
    }

筛选过程中，做了些许优化，很容易理解。单词按长度排序，长度小的一定不能由长度大的单词组成，自己不能组成自己。所以，我们才可以用一个单循环完成这些判别操作。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年04月25日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度