【动态规划】最长上升字符串、词语接龙问题_动态规划 单词接龙

【动态规划】最长上升字符串、词语接龙问题

• 最长上升字符串问题描述： 给一个字符串组成的列表，每个字符串都是上升字符串，例如‘aab’,'abc’都是上升字符串，将列表中的字符串随机组合，请问能连成的最长上升字符串的长度。
• 单词接龙问题描述：给一个字符串组成的列表， 问进行单词接龙能组成的最长字符串。
• 这两个问题实际是相同的，是一个多叉树搜索最大深度的问题，只不过每个节点有多少个叉，是动态的，取决于节点的特性。

每个节点有多少个叉？通过字典建立模型

该模型相当于动态规划中智能体的策略：p(a|x)，给定状态x，判断可行动作a有哪些。这里与上一篇博文中机器人走迷宫中的valid_actions()函数作用相同。

• 建立一个字典，key为所有的单词，value为该单词后面能接的所有单词列表。对于最长上升字符串问题，判断能不能接的条件就是后单词的首字母大于等于前单词的尾字母；对于单词接龙问题，条件就是后单词的首字母等于前单词的首字母。因此说两个问题是相同的。

def build_map(arr):
    ajmatrix = {
   }
    for i in range(len(arr)):
        ajmatrix[i] = []
    for i in range(len(arr)):
        for j in range(len(arr)):
            if i != j and smaller(arr[i],arr[j])<
1
2
3
4
5
6
7