Clever Geek Handbook

驯服回文症问题的动态

我不再是学生，但是在空闲时间，我将学习计算机科学的材料。我喜欢学习和分享。最近，我在著名的教科书“算法：构造与分析”中遇到了一个奇怪的问题。在本文中，我将演示使用此任务的动态编程原理。这很有趣，不是很复杂，并且您不需要编写任何其他数据结构或库来解决它。该措词适合一句话：



查找的字最长的回文序列w的长度n。



谁在乎，请照顾下。



不要混淆“子字符串”和“序列”的概念。第一个仅包含相邻的字母，第二个可以由彼此任意距离的字母组成。例如，在单词“数学”子序列将“罂粟”（米吃米大气压至a）中，“攻击”（米大气压厘米和TI KA）或“标记”（米大气压Ë毫安吨和KA）。 “回文”意味着必须从左到右和从右到左相等地读取子序列。一个字母的序列也将是回文的，尽管这是简并的情况。清楚的是，在一行中可以存在许多这样的肾盂次序列。我们对最长的感兴趣。如果w回文本身，那么答案将是整个字符串。否则，必须以某种方式寻找答案，例如，在单词“ brace”中，答案将为“ ooooo”。



听起来很简单，让我们开始分析。首先，让我们尝试解决“正面”问题。一个单词总共有多少个子序列n？很容易计算。组成子序列时，我们可以选择i不带字母th。事实证明，每个子序列都可以与带有n位的二进制数（可能从零开始）一一对应。由于只有这样的数字2^n，因此将减少一个子序列，因为我们不认为是空的。事实证明，搜索空间随增长呈指数增长n。这种一致性立即表明，做出正面决定是没有意义的。没有人想要一个即使在相对较小的行数（n = 1000）将执行几个世纪。整个计算机的要点是它们处理机械任务的速度比我们快得多，如果计算机运行的程序比一个人的时间长，那为什么值得“围着菜园”呢？



小题外话



总的来说，您是否想过算法运行时间的质性差异来自何处？为什么所有算法在线性时间内根本不起作用？从直觉上很清楚，执行时间取决于算法要解决的任务的复杂性（熵，信息量）。这种复杂性是什么？我想出了一个类比-这里需要将一定量的水从A点移至B点。如您所知，水是不可压缩的物质，因此只能倒入某个容器中。最初，我们不知道这个体积，只能带一个容器，尝试将所有水倒入其中，看看是否有溢出物。您可以随身携带几个不同大小的容器，如果我们决定不需要满满的容器，您甚至可以倒掉剩菜剩饭。



— "" , — , — , . .. "time-space trade-off" ( ), "" , . , , . " " , . -. "" "" "", "", . "" - , . , , . , . , - . — .



, . , , . (P vs. NP). ( " "), , .



.





. , . , — , . (), . " " , . , . . "" . , .. , .. :



  • .
  • , .. .


  • .


? , f . , f (.. "").



. w , . , ? , , . , . , , . , - .



, , . palindrome[i, j] w[i, j]. palindrome[1, n]. . , , palindrome[1, n]. ? , w[1, n-1], w[2, n], w[2, n-1]. w , w[1] + palindrome[2, n-1] + w[n]. :



  1. palindrome[j, i] = , j > i
  2. palindrome[i, i] = w[i].
  3. palindrome[i, j] = w[i] + palindrome[i + 1, j - 1] + w[j] w[i] = w[j]
  4. palindrome[i, j] = max{palindrome[i+1, j], palindrome[i, j-1], palindrome[i+1, j-1]}

    . , Python - :


def solve(s):
    palindromes = [['' for i in range(len(s))] for j in range(len(s))]
    n = len(s) - 1
    result = solve_memoized_rec(s, palindromes, 0, n)
    return result

def solve_memoized_rec(s, palindromes, i, j):
    if palindromes[i][j]:
        return palindromes[i][j]
    else:
        if i > j:
            solution = ''
        elif i == j:
            solution = s[i]
        elif s[i] == s[j]:
            prev = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = s[i] + prev + s[j]
        else:
            from_left = solve_memoized_rec(s, palindromes, i + 1, j)
            from_right = solve_memoized_rec(s, palindromes, i, j - 1)
            both = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = max(from_left, from_right, both, key=len)
        palindromes[i][j] = solution
        return solution


solve_memoized_rec palindromes, . , , . , - ( ). , , , . — . — , n (, ). , .. off-by-one error.



" ", " " palindromes. "". , "" palindromes[1, n].



:



def solve_iterative(s):
    n = len(s)
    palindromes = [['' for i in range(n)] for j in range(n)]
    for k in range(1, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if i == j:
                solution = s[i]
            elif s[i] == s[j]:
                solution = s[i] + palindromes[i + 1][j - 1] + s[j]
            else:
                solution = max(palindromes[i + 1][j], palindromes[i][j - 1], palindromes[i + 1][j - 1], key=len)
            palindromes[i][j] = solution
    return palindromes[0][n - 1]


, , i > j. , n^2.





, , . , !



我欢迎您对本文的内容和代码提出任何反馈。我的电报：@outofbound



More articles:


All Articles