"备忘录法算法-动态规划算法讲义"
动态规划是一种强大的算法，用于解决具有重叠子问题和最优子结构的问题。备忘录法是动态规划的一种实现策略，它通过存储先前计算过的子问题结果来避免重复计算，从而提高效率。在给出的代码示例中，`comb3`函数是一个典型的备忘录法应用，计算组合计数问题，即从n个不同元素中选择k个的不同组合数。
函数`comb3`首先初始化一个二维数组`dict`作为备忘录，用于存储已解决的子问题答案。然后，根据基本情况（n=k或k=0）返回1，表示空集或全集都是自身的组合。接着，函数利用备忘录检查是否已经计算过子问题`dict[n-1][k-1]`和`dict[n-1][k]`的结果，如果未计算过，则进行计算，并将结果存储回备忘录。最后返回当前子问题的答案，即`c1+c2`。
动态规划的经典问题之一是求两个序列的最长公共子序列（LCS）。LCS是指两个序列中存在一个序列，它是这两个序列的子序列且长度最长。例如，序列`A=xyxzyxyzzy`和`B=xzyzxyzxyzxy`的LCS是`xyxzxyzy`。
为了解决LCS问题，我们可以定义一个二维数组`c[i][j]`，其中`c[i][j]`表示序列`Xi`和`Yj`的LCS长度。对于边界情况（即`i=0`或`j=0`），LCS长度为0，因为没有元素。在其他情况下，LCS长度可以通过比较序列中的当前元素并选择两种可能性（不包含当前元素或包含当前元素但跳过另一个序列的下一个元素）中的较大值来计算。这个过程可以形成一个二维表格，其中每个单元格都表示特定子问题的解，通过这种方式避免了重复计算。
0-1背包问题也是动态规划的一个典型应用场景。在这个问题中，我们需要在一个容量为j的背包中选择价值最大的一组物品，每个物品都有自己的重量`w[i]`和价值`v[i]`，并且每件物品最多只能放入一次（0-1约束）。我们可以定义一个二维数组`m[i][j]`，其中`m[i][j]`表示在前i个物品中选取总重量不超过j的物品所能获得的最大价值。根据最优子结构，我们可以递归地计算`m[i][j]`，考虑包括第i个物品和不包括第i个物品两种情况，选择价值更大的那一种。
总结来说，动态规划通过备忘录法能够高效地解决复杂问题，避免重复计算，适用于诸如组合计数、最长公共子序列和0-1背包等问题。理解和熟练运用动态规划策略对于优化问题解决至关重要，因为它能够处理多种具有子问题重叠和最优子结构特点的实际问题。
我的内容管理
展开
