我经常对动态规划如何使用矩阵来解决问题感到困惑。 我大致理解矩阵用于存储先前子问题的结果，以便在处理更大问题时可以使用。
但是，如何确定矩阵的维数？我们如何知道矩阵的每一行/列应该表示什么值？即是否有通用的构建矩阵的过程？
例如，如果我们想使用面值为c1,c2,....cn的硬币更改S金额，矩阵的维度应该是多少？每个列/行应该代表什么？
任何指导都将有所帮助。 谢谢！
4个回答
14
一个问题可以使用动态规划解决，当它表现出重叠子问题和最优子结构时。其次，动态规划有两种变化：自底向上的Tabulation方法和自顶向下的记忆化方法（不是MemoRization!）。动态规划源于这样一种思想，一个大问题可以被进一步分解成子问题。自底向上的版本简单地开始解决这些子问题，并逐步构建目标解决方案。自顶向下的方法依赖于使用辅助存储来消除重新计算的需要。矩阵通常在Tabulation中使用，但并不总是需要一个矩阵。这里的主要目标是使子问题的解决方案随时可用，它可以存储在数组、矩阵甚至哈希表中。经典书籍Introduction to Algorithms展示了对切棒问题的两种解法，其中使用了一个一维数组作为辅助存储。如果我没有错的话，您指的是硬币找零问题的“总唯一方式”，即找到使用给定硬币集合构造给定金额的总方式数。有一个很好的视频可以很好地解释这个问题。它采用自下而上的方法: https://www.youtube.com/watch?v=DJ4a7cmjZY0。假设您需要从给定的硬币子集c = {1,2,10}构造金额n = 10，取一个空集并逐行添加来自c的硬币。对于每一行的下一个单元格，将添加一个来自该集合的硬币。列表示子问题。对于在n = 1 : 10中的i，第ith列表示使用该行中的硬币可以构建i的总方法数。
在这个表格中，
单元格是如何填充的？
最初，由0标头的整个第一列填充了1，因为无论你有多少硬币，对于金额0，你都只有一种找零的方法，即不找零。其余带有空子集
现在，我们如何填充{{X}}？你有两个选择，要么在这个新的超级集合中使用硬币{{1}}，要么不使用它。如果你不使用这个硬币，方法与上一行相同，即为{{0}}。但由于{{1}}可以用来找零{{1}}的金额，我们使用该硬币，并从金额{{1}}中减去{{1}}，以剩下{{0}}。现在查找同一行中{{0}}的方法，即为{{X}}之前的列，即为{{1}}。因此将其添加到顶部行的金额中，总计为{{1}}。所以你需要将这个单元格填充为{{1}}。
---------------------------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---------------------------------------------------------
|{} | | | | | | | | | | | |
---------------------------------------------------------
|{1} | | X | | | | | | | | | |
---------------------------------------------------------
|{1, 2} | | | | | | | | | | | |
---------------------------------------------------------
|{1, 2, 10}| | | | Y | | | | | | | Z |
---------------------------------------------------------
在这个表格中，
X代表使用硬币{1}构造金额1的方法数量，Y代表使用硬币{1, 2, 10}表示金额3的方法数量，Z代表使用硬币{1, 2, 10}表示金额10的方法数量。单元格是如何填充的？
最初，由0标头的整个第一列填充了1，因为无论你有多少硬币，对于金额0，你都只有一种找零的方法，即不找零。其余带有空子集
{}的第一行填充了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}}中减去{{1}}，以剩下{{0}}。现在查找同一行中{{0}}的方法，即为{{X}}之前的列，即为{{1}}。因此将其添加到顶部行的金额中，总计为{{1}}。所以你需要将这个单元格填充为{{1}}。
- Amal K
1
4我认为您现在应该明确说明（1）特定细胞如何初始化，以及（2）如何从先前的单元格计算X，以及为什么要这样做。 - Booboo
2
但是，如何确定矩阵的维数，以及我们如何知道矩阵的每行/列应该表示什么值？也就是说，有没有一种通用的构建矩阵的过程？
您需要找到递推关系和表示子问题所需的状态（参数数量）。DP的整个思想是避免重新计算子问题。第一次需要计算子问题时只计算一次，将其存储在内存中，并在需要时引用存储的值。因此，如果您想稍后引用子问题的存储结果，则需要具有唯一标识子问题的密钥。子问题的状态通常是此键的很好选择。如果一个子问题具有3个参数code> x ，
能够解决DP问题（任何递归问题）的最重要步骤是识别并能够写下递推关系。一旦确定了递推关系，我会说完成90％的工作。让我们首先看看如何编写递推关系。
任何递归问题中的三个重要思想是
在上面的
现在让我们尝试推导一些DP问题的递归关系。您应该能够从递归关系中推导出状态的维度（因此您对矩阵维度的困惑）。
记住，要找到递归关系，我们需要确定子问题。确定子问题并不总是直截了当的。需要通过更多的DP问题来练习，以获得更好的洞察力，并识别模式，进行试错等。
让我们为两个看起来几乎相似但需要不同方法的问题确定递归关系。我选择这个问题只是因为问题涉及到矩阵的维度。
给定不同面额的硬币和一个金额，在这些硬币中找出能够组成该金额所需的最少硬币数。
让我们将寻找给定金额n所需的最小硬币数的问题/算法表示为
如果我们知道
因此，这里的子问题是
因此递归关系为：
现在我们允许下一个面额 q，然后解决以下递归问题。
最后，
以上三个递归关系通常可以写成以下形式，其中
从递归关系可以看出，你需要两个状态变量来表示子问题，因此需要一个2D数组或哈希表，通过这两个值的组合（例如元组）作为键来缓存子问题的结果。
另请参见Thought process for arriving at dynamic programming solution of Coins change problem。
y ， z ，则元组 （x的值，y的值，z的值） 是在哈希表中存储子问题结果的良好键。如果这些值是正整数，可以使用矩阵即多维数组代替哈希表。让我们开发找到递归关系和识别所需状态以唯一表示子问题的思路，以便解决您对矩阵维度的困惑。
能够解决DP问题（任何递归问题）的最重要步骤是识别并能够写下递推关系。一旦确定了递推关系，我会说完成90％的工作。让我们首先看看如何编写递推关系。
任何递归问题中的三个重要思想是
- 识别出平凡的情况（其答案已知的基本情况），
- 确定如何将问题分解为子问题
- 知道如何组合子问题的结果。
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)，F(n-q)和F(n-r)的答案，即分别组成金额n-p，n-q和n-r所需的最小硬币数，我们可以取这些值中的最小值加1，得到组成金额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只需要一个参数，即一个参数足以表示递归树中的子问题/节点，因此可以使用1D数组或键为单个值的哈希表来存储子问题的结果。
- 给定不同面额的硬币和一个金额，找出组成该金额所需的硬币总组合数。
这个问题更加微妙。暂停一下并尝试识别递推关系。
让我们使用与上述问题相同的术语，即假设金额为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
从递归关系可以看出，你需要两个状态变量来表示子问题，因此需要一个2D数组或哈希表，通过这两个值的组合（例如元组）作为键来缓存子问题的结果。
另请参见Thought process for arriving at dynamic programming solution of Coins change problem。
- Shashank V
1
这一章非常好地解释了它：http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf。在第178页，它提供了一些方法来识别子问题，使您能够应用动态规划。
- Bogdan
-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维矩阵。
- dfb
1
1我在这里没有看到任何关于如何将这个问题表示为矩阵的解释？ - Robin Andrews
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接