记忆化搜索

我们用记忆化搜索（DFS+Memoization）来引出动态规划。其实记忆化搜索约等于动态规划，只不过在实现和细节表现上有一些区别。

讨论：动态规划（DP）与记忆化搜索（Memoization）的优劣比较：

记忆化搜索最大的优点： 1. 容易编写，不需要注意转移顺序，比如区间DP中要先枚举长度避免overwrite状态，也不用注意要先declare足够的数组空间。 2.在有些情况下可以减少访问的状态。相比之下动态规划一般需要访问所有的子问题。这一点一般情况下区别不大，因为两者相比时间复杂度都是相似的。

记忆化搜索最大的缺点

1.因为迭代调用函数，常规时间常数可能较大 2.不能用滚动数组来优化空间。

在算法思维上，DP和贪心与分治都很相似。然而DP的特点是它具有：

最优子结构：通过遍历子问题的答案，做出最有选择。其中子问题没有共享资源(no shared resources between subproblems)。因为要遍历所有子问题才能找到最后答案，这点区别于贪心。
重叠子问题：在遍历子问题的过程中，没有产生新的问题（not generating new problems）。这点区别于分治。

OIWiki里有很好的例题介绍了记忆化搜索来引出动态规划。类似的题目数不胜数，下面这个例子用了Memoization，二维DP，和一维滚动数组DP求解。

例题：恰有 K 根木棍可以看到的排列数目

有 n 根长度互不相同的木棍，长度为从 1 到 n 的整数。
请你将这些木棍排成一排，并满足从左侧 可以看到 恰好 k 根木棍。
从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。

例如，如果木棍排列为 [1,3,2,5,4] ，那么从左侧可以看到的就是长度分别为 1、3 、5 的木棍。
给你 n 和 k ，返回符合题目要求的排列 数目 。

输入：n = 3, k = 2
输出：3
解释：[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。

def rearrangeSticks(n, k):
    MOD = 10**9 + 7
    @cache
    def helper(n, k):
        if k==0: return 0
        if k==n: return 1            
        res = helper(n-1, k-1) % MOD + helper(n-1, k)*(n-1) % MOD
        return res % MOD
    return helper(n, k)

def rearrangeSticks(n, k):
    MOD = 10**9 + 7
    f = [[0]*(k+1) for _ in range(n+1)]
    f[0][0] = 1
    for i in range(1, n+1):
        for j in range(1, k+1):
            f[i][j] = f[i-1][j-1]
            if i>j:
                f[i][j] += (i-1)*f[i-1][j]
            f[i][j] %= MOD
    return f[-1][-1]

def rearrangeSticks(self, n: int, k: int) -> int:
    MOD = 10**9 + 7
    f = [1] + [0]*k
    for i in range(1, n+1):
        g = [0]*(k+1)
        for j in range(1, k+1):
            g[j] = (f[j-1] + f[j]*(i-1)) % MOD
        f = g
    return f[-1]

Previous动态规划 Next线性DP

Last updated 4 years ago

hashtag例题：恰有 K 根木棍可以看到的排列数目arrow-up-right

例题：恰有 K 根木棍可以看到的排列数目