leetcode 周赛速递 | 1048 DAG动态规划
这几天在看动态规划的题目，看的不多，但是学到了一个很重要的概念，那就是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 <= 10001 <= words[i].length <= 16words[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上的动态规划
点赞的时候，请宠溺一点
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
