我总是对动态编程如何使用矩阵来解决问题感到困惑.我粗略地理解矩阵用于存储先前子问题的结果,因此它可以用于以后计算更大的问题.
但是,如何确定矩阵的维数,以及我们如何知道矩阵的每一行/列应该代表什么值？即,是否有像构建矩阵的通用程序？
例如,如果我们有兴趣使用值为c1,c2,...... cn的硬币来更改S金额,那么矩阵的维度应该是多少,每列/行应代表什么？
任何方向指导都会有所帮助 谢谢!
当一个问题同时表现出重叠子问题和最优子结构时，它就有资格进行动态规划。
其次，动态规划有两种变体：
动态规划源于这样一种意识形态，即一个大问题可以进一步分解为子问题。自下而上的版本只是首先解决这些子问题，然后逐步构建目标解决方案。自上而下的方法依赖于使用辅助存储来消除重新计算。
是否有构建矩阵的通用程序？
这实际上取决于您正在解决什么问题以及您如何解决它！矩阵通常用于制表，但它始终不必是矩阵。这里的主要目标是根据需要随时提供子问题的解决方案，它可以存储在数组、矩阵甚至哈希表中。
经典书籍《算法导论》以两种方式演示了使用一维阵列作为辅助存储的棒切割问题的解决方案。
例如，如果我们有兴趣使用价值为 c1,c2,....cn 的硬币对 S 金额进行更改，那么矩阵的维数应该是多少，每列/行应该代表什么？
如果我没记错的话，您指的是硬币找零问题的“完全独特的找零方式”变体。您需要找到使用给定的一组硬币构造给定数量的总方式。有一个很棒的视频可以很好地分解它。它使用自下而上的方法：https : //www.youtube.com/watch?v=DJ4a7cmjZY0
假设您需要n = 10从给定的硬币子集构建数量c = {1, 2, 10}
取一个空集并继续从 中每行添加一个硬币c。对于下一行，从集合中添加一枚硬币。列代表子问题。对于iin n = 1 : 10，第ith 列表示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}。
细胞是如何填充的？
最初，0以1s开头的整个第一列都填充了s，因为无论您有多少硬币，对于数量 0，您都只有一种方法可以找零，那就是不找零。带有空子集的第一行的其余部分{}用0s填充，因为您无法在没有硬币的情况下对任何正金额进行更改。现在矩阵看起来像这样：
--------------------------------------------------------
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.
dfb*_*dfb -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 维矩阵。