专栏首页ACM算法日常leetcode 周赛速递 | 1048 DAG动态规划

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

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

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

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

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

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

题目如下:

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

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

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

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

示例:

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

提示:

  1. 1 <= words.length <= 1000
  2. 1 <= words[i].length <= 16
  3. 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;
    }
};

参考资料:

《算法竞赛入门经典(第2版)》第9章 DAG上的动态规划

点赞的时候,请宠溺一点

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第八届福建省大学生程序设计竞赛 | FZU2280 Magic

    Kim is a magician, he can use n kinds of magic, number from 1 to n. We use strin...

    ACM算法日常
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 简单ac自动机学习

    简单的来讲解一下自动机,虽然都在说这是和的组合,但个人觉得不需要深入理解这两个仍然可以学会它。同时由于网上已经存在了很多教程,本文尽量避免采取和网上一样的说法,...

    ACM算法日常
  • 经典算法学习之回溯法

    回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

    用户1215536
  • LeetCode 30 Substring with Concatenation of All Words

    ShenduCC
  • HDU-2588-GCD

    ACM模版 描述 ? 题解 image.png 代码 #include <stdio.h> #include <math.h> int Euler(int n...

    f_zyj
  • Data Structure_图

    交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

    西红柿炒鸡蛋
  • Data Structure_图图论带权图

    交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

    西红柿炒鸡蛋
  • 逆元(个人模版)

    逆元: 1 int ex_gcd(int a,int b,int &x,int &y) 2 { 3 if(b==0) 4...

    Angel_Kitty
  • BUPT2017 wintertraining(15) #1 题解

    求逆元。以前写过题解,http://www.cnblogs.com/flipped/p/5193777.html

    饶文津

扫码关注云+社区

领取腾讯云代金券