leetcode 周赛速递 | 1048 DAG动态规划

ACM算法日常

发布于 2019-05-28 09:38:32

1.4K00

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

这几天在看动态规划的题目，看的不多，但是学到了一个很重要的概念，那就是DAG上的动态规划。

DAG英文翻译是Directed acyclic graph，也就是有向无环图，如下图。

动态规划其实也是从一个状态跳转到另外一个状态，有方向和路径。

动态规划和DAG的共同特性使得动态规划的一些题目在用DAG思路来解决的适合非常容易思考，DAG模型非常易于掌握，也非常强大。

今天leetcode周赛上的第三题就是一个典型应用，让我们一起看看。

题目如下：

给出一个单词列表，其中每个单词都由小写英文字母组成。

如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。

从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。

示例：

输入：["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] 仅由小写英文字母组成。

首先这道题看完后就能很简单的建立一个DAG模型，示例图如下：

DAG的题目有一个通用解题模型，基本上属于0思考就能解决这道动态规划题目。dp函数通常如下：

    int dp(int i){
        if(d[i] > 0){
            return d[i];
        }

        int m = 1;

        for(int j=0; j<words_->size(); ++j){
            if(isnext(i, j)){
                m = std::max(m, dp(j)+1);
            }
        }

        d[i] = m;

        return m;
    }

};

解题源代码：C++

#define SIZE_HASH 2000

class Solution {
public:
    int d[10000];
    vector<string> * words_;
    int * next;

    bool isnext(int i, int j){
        int hash = i*SIZE_HASH+j;

        if(next[hash] != -1){
            return next[hash];
        }

        vector<string> & words = *words_;

        string & si = words[i];
        string & sj = words[j];

        if(si.length() - sj.length() != -1){
            next[hash] = 0;
            return false;
        }

        int v = 1;
        int pi = 0;
        int pj = 0;
        for(int pj=0; pj<sj.length(); ++pj){
            if(sj[pj] != si[pi]){
                if(v>0){
                    v--;
                }else{
                    next[hash] = 0;
                    return false;
                }
            }else{
                pi++;
            }
        }
        next[hash] = 1;
        return true;
    }

    int dp(int i){
        if(d[i] > 0){
            return d[i];
        }

        int m = 1;

        for(int j=0; j<words_->size(); ++j){
            if(isnext(i, j)){
                m = std::max(m, dp(j)+1);
            }
        }

        d[i] = m;

        return m;
    }

    int longestStrChain(vector<string>& words) {
        this->words_ = &words;
        memset(d, 0, 10000);
        next = new int[SIZE_HASH*SIZE_HASH];
        for(int i=0; i<SIZE_HASH*SIZE_HASH; ++i){
            next[i] = -1;
        }

        int m = 1;
        for(int i=0; i<words.size(); ++i){
            m = std::max(m, dp(i));
        }
        return m;
    }
};