分析动态编程，装饰器功能和经典问题（LCS，DAG，背包问题，序列比对

专门针对算法设计的应用程序，动态编程技术的核心实际上是一种缓存.

在正常情况下，动态编程算法会反转相应的递归函数，以进行迭代迭代和填充某些数据结构. 填充对象可以是某种多维数组.

因为我们使用Python，所以我们有另一个选择. 当实现相关的递归函数时，我们可以直接从缓存中返回值. 这里将介绍存储的概念. 内存化的方式是我们可以使用相同的参数执行多个调用，以便返回的结果将直接来自缓存.

尽管存储器技术可以使动态编程的基本原理更加明显，但在许多情况下，由于堆栈深度的限制和函数调用的成本，最好选择一种迭代方案.

在这里，我们可以首先介绍第一个小问题，找到一组数字中最长的递增（或非递减）子序列，如果有多个，则找到其中一个. 此外，序列中的元素必须在子集中保持其原始顺序.

例如，对于序列[3，1，0，2，4]背包问题 动态规划 python，[1,2,4]是一个解决方案.

这是蛮力解决方案. 尽管sorted使用sorted函数，但它在itertools中也调用了combination函数. 但是此解决方案仅会生成可能的序列. 在最坏的情况下，运行时间仍然是指数的:

# 朴素版本的最长递增子序列算法
from itertools import combinations
def native_lis(seq):
    for length in range(len(seq), 0, -1):
        for sub in combinations(seq, length):
            if list(sub) == sorted(sub):
                return sub

然后，我们继续研究斐波那契数列和帕斯卡三角形的两个经典问题:

让我们先谈谈斐波那契数列. 此序列易于实现. 让我们直接转到Python代码:

# Python斐波那契数列
def fib(i):
    if i < 2:
        return 1
    return fib(i-1) + fib(i-2)

但是我们可以输入fib（10），很快就能给我们答案，但是当我们输入fib（100）时，程序将直接卡住:

为了解决这个问题，这里直接提供解决方案. 此代码封装了带有嵌套字段的临时函数. 当然，您也可以使用具有缓存功能和func属性的类来实现相同的功能. 以下是代码实现:

# 记忆体化的装饰器的函数
from functools import wraps
def memo(func):
    cache = dict()
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

这时我们可以直接尝试:

这一次完全没有问题，结果将很快可用. 这个内存函数的想法是缓存自己的返回值. 如果您在相同的参数中将他视为一种缓存逻辑，但是备忘功能更可重用. 这里被设计成装饰器.

类似地，对于帕斯卡三角形问题:

帕斯卡三角形如上所示.

这个问题实际上更实际: 二项式系数的计算. 也就是说，组合函数C（n，k）意味着我们要从n个数字的集合中找到k个数字的子集.

第一步通常是找到某种递归或递归分解的方法. 此时，我们可以通过判断是否包含该元素来分解问题. 对于此操作，我们可以按元素顺序进行操作，因此在C（n，k）的单次求值中，您只需要担心元素当前是否存在n个数. 在其中，我们检查了n-1个元素的k-1个大小子集. 如果元素不在其中，请检查其k大小的子集.

对于单个空子集C（n，0）= 1;对于空集的非空子集，C（0，k）= 0，k> 0.

为什么说Pascal三角形，是因为该递归公式对应于Pascal三角形. 如图C（4,2）所示，对应的数字为6，计算方法为C（3,1）+ C（3,2）= 3 + 3 = 6.

@memo效率有很大差异. 读者可以自己尝试.

然后，我们讨论另一个问题，即有向无环图中的最短路径问题:

动态编程的核心实际上是决策顺序的问题.

在有向无环图中找到从一个点到另一个点的路径是一个典型的决策序列问题.

下图是带有权重和标签的DAG拓扑图. 突出显示的部分代表从a到f的最短路径:

这是一个连续的决策过程.

我们可以直接实现递归，这样某些单词问题将变成指数运算，但是这些问题可以被记住，这是一个线性级算法，对于n个节点和m个边图，运行时间为Θ（n + m） :

# 运用递归/记忆体化的方式来解决DAG的最短路径问题
def rec_dag_sp(W, s, t):
    @memo
    def d(u):
        if u == t:
            return 0
        return min(W[u][v]+d(v) for v in W[u])
    return d(s)

删除@memo后，该算法将成为指数运算.

但是对于迭代解决方案，我们需要一个独立的拓扑排序. 然后是一个更常见的迭代方案:

# DAG的最短路径问题
def dag_sp(W, s, t):
    d = {u:float(int) for u in W}
    d[s] = 0
    for u in topsort(W):
        if u == t:
            break
        for v in W[u]:
            d[v] = min(d[v], d[u] + W[u][v])
    return d[t]
# 有向无环路图的拓扑排序
def topsort(G):
    count = dict((u, 0) for u in G)
    for u in G:
        for v in G[u]:
            count[v] += 1
    Q = [u for u in G if count[u] == 0]
    S = []
    while Q:
        u = Q.pop()
        S.append(u)
        for v in G[u]:
            count[v] -= 1
            if count[v] == 0:
                Q.append()
    return S

这种迭代算法的想法是尝试放松我们面前所有可能节点的边缘. 因此，我们放宽了当前节点的输入边缘.

接下来，我们继续研究下一个问题，我们前面也提到过，它是子序列增长最快的问题:

在这个问题中我们允许相同的值. 如前所述，我们直接在此处提供代码实现:

# 最长递增子序列问题
# 用记忆体、递归方式解决最长子序列问题
def rec_lis(seq):
    @memo
    def L(cur):
        res = 1
        for pre in range(cur):
            if seq[pre] <= seq[cur]:
                res = max(res, 1 + L(pre))
        return res
    return max(L(i) for i in range(len(seq)))

以下是相应的迭代版本:

# 用基本迭代方式解决最长递增子序列问题
def basic_lis(seq):
    L = [1] * len(seq)
    for cur, val in enumerate(seq):
        for pre in range(cur):
            if seq[pre] <= val:
                L[cur] = max(L[cur], 1 + L[pre])
    return max(L)

迭代版本可能看起来比递归版本更好. 其中两个的实现代码基本相似.

DAG算法的思想是将序列中的每个元素视为图中的一个节点，并且在每个节点与大于它的节点之间将存在一个隐藏边. 对于所有合格的候选节点，其子序列将不断增加. 就像下面的图片一样:

这是一个数字序列，每个递增序列的DAG都隐藏在其中. 突出显示的部分是序列中最长的递增子序列.

该算法的主要时间片集中在搜索操作上. 如果搜索是线性操作，我们可以将其替换为二进制搜索.

实现直接在下面给出:

# 最长递增子序列问题
from bisect import bisect
def lis(seq):
    end = []
    for val in seq:
        idx = bisect(end, val)
        if idx == len(end):
            end.append(val)
        else:
            end[idx] = val
    return len(end)

接下来，我们继续下一个问题，即序列比较问题:

关于序列比较的问题，我们说这两个问题是两个序列之间的最长公共子序列（LCS）及其编辑距离.

编辑距离是指将一个序列更改为另一序列所需的编辑操作，包括插入，删除和替换.

如果将序列设置为a和b，则下标为i和j. 目前，存在三种情况，表示为函数:

实现如下:

# 序列对比问题
# 用递归、记忆体化的方式解决LCS问题
def rec_lcs(a, b):
    @memo
    def L(i, j):
        if min(i, j) < 0:
            return 0
        if a[i] == b[j]:
            return 1 + L(i-1, j-1)
        return max(L(i-1, j), L(i, j-1))
    return L(len(a)-1, len(b)-1)

上面的递归分解操作，我们可以简单地将其视为一个动态决策过程. 上图:

上图是LCS问题的基本DAG. 水平和垂直方向上的边在顶部为0，而角是最长的路径. 突出显示的部分是问题的LCS.

然后将其反转为迭代模式，如下所示:

# 用迭代方法解决LCS问题
def lcs(a, b):
    n, m = len(a), len(b)
    pre, cur = [0]*(n+1), [0]*(n+1)
    for j in range(1, m+1):
        pre, cur = cur, pre
        for i in range(1, n+1):
            if a[i-1] == b[j-1]:
                cur[i] == pre[i-1] + 1
            else:
                cur[i] = max(pre[i], cur[i-1])
    return cur[n]

然后我们继续下一个问题. 背包问题:

贪婪算法中提到了整数背包问题. 尽管贪婪算法无法解决，但我们可以使用动态规划技术完全解决它.

首先讨论整数背包问题:

让背包的剩余容量为r（m）. r的每个值代表一个子问题. 我们的递归分解围绕背包内容的最后一个单位是否有用进行. 如果不使用，则有m（r）= m（r-1）. 如果有用，请选择正确的对象. 如果是i，则m（r）= v [i] + m（r-w [i]）. 加i时，还会使用剩余容量中某个位置的质量.

以下是代码实现:

# 用递归、记忆体化方式解决无限制的整数背包问题
def rec_unbounded_knapsack(w, v, c):
    @memo
    def m(r):
        if r == 0:
            return r
        val = m(r-1)
        for i, wi in enumerate(w):
            if wi > r:
                continue
            val = max(val, v[i] + m(r-wi))
        return val
    return m(c)

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-188263-1.html