我总是对动态编程如何使用矩阵来解决问题感到困惑。我大致了解该矩阵用于存储先前子问题的结果，以便在以后计算更大的问题时使用它。
但是，如何确定矩阵的维度，以及我们如何知道矩阵的每一行/列应该代表什么值？即，是否有构建矩阵的通用程序？
例如，如果我们有兴趣使用价值 c1,c2,..cn 的硬币来更改 S 金额，那么矩阵的维度应该是多少，每列/行应该代表什么？
任何方向性的指导都会有所帮助。谢谢！
问问题
6352 次
4 回答
12
当一个问题同时表现出重叠子问题和最优子结构时，它就符合动态规划的条件。
其次，动态规划有两种变体：
- 制表法或自下而上法
- 记忆化或自上而下的方法（不是记忆
化！）
动态规划源于这样一种思想，即一个大问题可以进一步分解为子问题。自下而上的版本只是首先解决这些子问题，然后逐步构建目标解决方案。自上而下的方法依赖于使用辅助存储来消除重新计算。
是否有构建矩阵的通用程序？
这实际上取决于您要解决什么问题以及如何解决它！矩阵通常用于制表，但它总是不必是矩阵。这里的主要目标是按需提供子问题的解决方案，它可以存储在数组、矩阵甚至哈希表中。
经典书籍Introduction to Algorithms演示了使用一维数组作为辅助存储的两种方式来解决切杆问题。
例如，如果我们有兴趣使用价值 c1,c2,..cn 的硬币来更改 S 金额，那么矩阵的维度应该是多少，每列/行应该代表什么？
如果我没记错的话，您指的是硬币找零问题的“完全独特的找零方式”变体。您需要找到使用给定的一组硬币构建给定数量的总方法。有一个很棒的视频可以很好地分解它。它使用自下而上的方法：https ://www.youtube.com/watch?v=DJ4a7cmjZY0
假设您需要n = 10从给定的硬币子集构造数量c = {1, 2, 10}
取一个空集并继续从 中每行添加一个硬币c。对于下一行，从该组中添加一个硬币。列代表子问题。对于iin n = 1 : 10，第th 列表示可以使用该行中的硬币构建i的方式总数：i
--------------------------------------------------------
|0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
--------------------------------------------------------
|{} | | | | | | | | | | | |
--------------------------------------------------------
|{1} | | X | | | | | | | | | |
--------------------------------------------------------
|{1, 2} | | | | | | | | | | | |
--------------------------------------------------------
|{1, 2, 10}| | | | Y | | | | | | | Z |
--------------------------------------------------------
在此表中，X表示金额 1 可以使用硬币构造的方式数量{1}，Y表示金额 3 可以使用硬币表示的方式数量，{1, 2, 10}以及Z 表示金额 10 可以使用硬币表示的方式数量{1, 2, 10}。
细胞是如何填充的？
最初，以 s 为标题的整个第一列0都是用 s 填充的，1因为无论你有多少硬币，对于金额 0，你只有一种方法来找零，那就是不找零。具有空子集的第一行的其余部分{}用 s 填充，0因为您无法在没有硬币的情况下对任何正数进行更改。现在矩阵看起来像这样：
--------------------------------------------------------
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
--------------------------------------------------------
|{} |1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
--------------------------------------------------------
|{1} |1 | X | | | | | | | | | |
--------------------------------------------------------
|{1, 2} |1 | | | | | | | | | | |
--------------------------------------------------------
|{1, 2, 10}|1 | | | Y | | | | | | | Z |
--------------------------------------------------------
现在，我们如何填充X？你有两种选择，要么使用1这个新超级套装中的硬币，要么不使用它。如果您没有使用硬币，方法与上一行相同0。但是由于1可以用来改变金额1，我们使用那个硬币，并从剩下1的金额中减去。现在在同一行中查找 ,的方式，即在其之前的列是。因此，将其添加到顶行的金额中，总计为. 因此，您将此单元格填充为.100X111
于 2020-06-20T16:45:07.517 回答
2
但是，如何确定矩阵的维度，以及我们如何知道矩阵的每一行/列应该代表什么值？即，是否有构建矩阵的通用程序？
您需要找到表示子问题所需的递归关系和状态（参数数量）。DP的整个想法是避免重新计算子问题。您只在第一次需要子问题时计算一次，将其存储在内存中，并在需要时引用存储的值。所以如果你以后想引用一个子问题的存储结果，你需要有一个唯一标识子问题的键。子问题的状态通常是这个键的好选择。如果一个子问题有 3 个参数x, y, z, 那么一个元组(value of x, value of y, value of z)例如，将子问题的结果存储在哈希表中是一个很好的键。如果这些值是正整数，您可以使用矩阵，即多维数组，而不是哈希表。让我们发展寻找递归关系和识别唯一表示子问题所需的状态的想法，以便消除您对矩阵维度的混淆。
能够解决 DP 问题（通常是任何递归问题）的最重要步骤是识别并能够写下递归关系。一旦确定了递归关系，我会说 90% 的工作已经完成。我们先来看看如何写出递推关系。
任何递归问题中的三个重要思想是
- 识别琐碎案例（答案已知的基本案例），
- 确定如何将问题划分为子问题
- 知道如何组合子问题的结果。
我们以归并排序为例。这不是 DP 问题，因为没有重叠的子问题，但是为了引入递归关系，它是一个很好的选择，因为它很有名且易于理解。您可能已经知道，归并排序中最简单的情况是大小为 0 或 1 的数组。递归步骤是将问题分成两个大小为当前问题一半大小的子问题，组合步骤是合并算法。最后我们可以写出归并排序的递归关系如下：
sort(0, n) = merge(sort(0, n/2), sort(n/2, n))
在上述sort算法的递推关系中，范围(0,n)的问题分为(0,n/2)和(n/2,0)两个子问题。组合步骤是合并算法。
现在让我们尝试推导一些 DP 问题的递归关系。您应该能够从递归关系中得出状态的维度（以及因此您对矩阵维度的混淆）。
请记住，要找到递归关系，我们需要识别子问题。识别子问题并不总是那么简单。只有实践更多的 DP 问题才能对这些问题有更好的直觉，并识别模式、反复试验等。
让我们确定两个看起来几乎相似但需要不同方法的问题的递归关系。我选择这个问题只是因为问题是关于矩阵维度的混淆。
- 给定不同面额和数量的硬币，找出产生该数量所需的最小硬币数量。
让我们将寻找给定数量 n 所需的最小硬币数量的问题/算法表示为F(n)。如果面额是 p、q、r。
如果我们知道和的答案F(n-p)，即分别产生 np、nq 和 nr 所需的最小硬币数量，我们可以取这些和 1 中的最小值来获得产生数量所需的硬币数量。F(n-q)F(n-r)n
这里的子问题是和F(n-p)， 组合步骤是取这些值中的最小值并加一。F(n-q)F(n-r)
所以递归关系为：
F(n) = min(F(n-p), F(n-q), F(n-r)) + 1
# Base conditions
F(0) = 0
F(n) = infinity if n < 0
存在最优子结构，存在重复问题（如果不明显，就抽取一个样本问题绘制递归树），所以我们可以使用一些存储来避免重复计算。每个子问题都是递归树中的一个节点。
从递归关系可以看出，函数 F 只接受一个参数，即一个参数足以表示递归树中的子问题/节点，因此可以使用一维数组或由单个值键控的哈希表来存储子问题的结果。
- 给定不同面额的硬币和数量，找出需要的硬币组合总数。
这个问题比较微妙。停下来想一想，试着找出递归关系。
让我们使用与上述问题相同的术语，即假设金额是 n，p、q、r 是面额。
与上述问题相同的重复是否有效？如果F(n)表示从给定面额中构成 n 的计数组合的总数，我们可以组合F(n-p)，F(n-q)并且F(n-r)有某种方法可以得到 F(n) 吗？添加它们怎么样？F(n) = F(n-p) + F(n-q) + F(n-r)持有吗？
取 n = 3 和两个面额 p, q = 1, 2
通过上面的递归关系，我们得到答案为 3，对应于拆分 [1, 1, 1], [1, 2], [2, 1] 这是不正确的，因为 [1, 2] 和 [2, 1] 是相同的教派组合。上面的递归是计算排列而不是组合的数量。为了避免重复的结果，我们需要整理硬币。我们可以通过强制 p 在 q 之前并且 q 在 r 之前来自己选择它。关注每个面额的组合数量。由于我们自己在可用面额 [p, q, r] 中执行订单。
让我们从 p 开始并解决以下递归。
F(n, only p allowed) = F(n-p, only p allowed)
## Base condition
F(0) = 1 # There is only one way to select 0 coins which is not selecting any coinss
现在让我们允许下一个面额 q，然后求解下面的递归。
F(n, p and q allowed) = F(n-q, p and q allowed) + F(n, only p allowed)
最后，
F(n, p q and r allowed) = F(n-r, p q and r allowed) + F(n, p and q allowed)
上述三个递推关系一般可以写成如下形式，其中i是面额中的索引。
# F(n, i) = with denominations[i] + without denominations[i]
F(n, i) = F(n - denominations[i], i) + F(n, i-1)
## Base conditions
F(n, i) = 1 if n == 0
F(n, i) = 0 if n < 0 or i < 0
从递归关系中，我们可以看到您需要两个状态变量来表示一个子问题，因此需要一个二维数组或一个以这两个值组合为键的哈希表（例如元组）来缓存子问题的结果。
于 2020-06-20T20:47:40.747 回答
1
本章很好地解释了它：http ://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf 在第 178 页，它提供了一些方法来识别允许您应用动态规划的子问题。
于 2013-03-13T21:20:47.280 回答
-2
DP 解决方案使用的数组几乎总是基于问题状态空间的维度——即每个参数的有效值
例如
fib[i+2] = fib[i+1] + fib[i]
是相同的
def fib(i):
return fib(i-1)+fib(i-2]
您可以通过在递归函数中实现记忆化来使这一点更加明显
def fib(i):
if( memo[i] == null )
memo[i] = fib(i-1)+fib(i-2)
return memo[i]
如果你的递归函数有 K 个参数，你可能需要一个 K 维矩阵。
于 2013-03-13T20:11:40.907 回答