我正在学习动态编程，遇到了这个著名的硬币变化问题。
解决此问题的递归关系由下式给出
countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);
优化问题的最简单方法是存储子问题的解。所以我为(sum,i)的每个值维护了一个Map。那里不再解决同样的问题。
String key = sum + ":" + i;
Integer memoizedVal = results.get(key);
if (memoizedVal != null) {
return memoizedVal;
}
下一个优化级别是有一个 2Dn X sum表，其中 n 是集合中的元素数。
从递归关系中很容易理解，(arr, sum - arr[i], i)转换为同一行中的DP[sum-arr[i]]。(因为i是一样的(
(arr, sum, i - 1)转换为DP[i-1](sum列中的上一行(。
带有2D矩阵的完整解决方案如下所示。
public static int countWaysDP2D(int[] arr, int sum) {
int[][] table = new int[arr.length][sum + 1];
table[0][0] = 1;
for (int i = 1; i <= sum; i++) {
table[0][i] = 0;
}
for (int j = 1; j < arr.length; j++) {
table[j][0] = 1;
}
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= sum; j++) {
int sumWithI = j - arr[i-1] < 0 ? 0 : table[i][j - arr[i-1]];
int sumWithoutI = table[i - 1][j];
table[i][j] = sumWithI + sumWithoutI;
}
}
return table[arr.length - 1][sum];
}
但是方法2中给出的灵魂仅使用1D数组，如下所示
public static int countWaysDP1D(int[] arr, int sum) {
int[] table = new int[sum + 1];
table[0] = 1;
for (int i = 0; i < arr.length; i++) {
for (int j = arr[i]; j <= sum; j++) {
table[j] += table[j - arr[i]];
}
}
return table[sum];
}
仅使用 1D 阵列背后的逻辑是什么？我测试了许多输入值，结果与 2D 数组相同。二维阵列解决方案如何转换为一维阵列？
我的意思是所有的初始条件都去哪儿了？(0th row和0th column(
对于第j个 for 循环，为什么它从数组中的第j个元素迭代，直到sum递增1？真的很难想象所有这些。有人可以一步一步地解释这种转变吗？
从递归关系countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);，很明显你需要大小len(arr) x (sum+1)的二维数组/表来存储结果。我们将从表格的左上角到右下角依次填充表格，我们的答案是右下角单元格的值。您需要两个值来填充表的每个单元格table[i, sum - arr[i]] and table[i - 1, sum]。
考虑填充一行 - 第 0 个单元格的值为 1，所有其他单元格的开头值为 0。要更新单元格，我们需要查找同一行中的table[i, sum - arr[i]]。对于table[i - 1, sum]，我们需要查找前一行。我们不需要任何其他行。所以实际上我们只需要 2 行空间，我们可以将其中一行视为前一行，另一行视为正在填充的当前行。
现在考虑使用只有 2 行2 x (sum+1)表来解决问题。考虑第 1 行是当前正在填充的行，第 0 行是已填充的前一行。 假设 arr = [2， 3， 7]。因此，您按如下方式填充第 1 行。
table[1, 0] = table[0, 0]
table[1, 1] = table[0, 1]
table[1, 2] = table[0, 2]
table[1, 3] = table[1, 0] + table[0, 3]
table[1, 4] = table[1, 1] + table[0, 4]
table[1, 5] = table[1, 2] + table[0, 5]
...
观察上述等式后，计算第 1 行的另一种方法是将第 0 行复制到未填充的第 1 行，然后按如下方式填充第 1 行
Copy row 0 onto row 1
table[1, 3] += table[1, 0]
table[1, 4] += table[1, 1]
table[1, 5] += table[1, 2]
我们可以重用第 0 行本身，而不是将第 0 行复制到未填充的行 1 上。所以算法的最终空间高效头像是 - 取一行大小 (sum+1(。指定 row[0] = 1 作为基本条件。我们填充第 0 行或任何其他行的方式没有区别，因为我们现在进行的唯一查找是在上面显示的同一行中。
// Pseudo code
create row of size (sum+1)
row[0] = 1 // base condition
fill rest of the row with zeros
for element in arr: /* for (int i = 0; i < arr.length; i++) */
from column j where j - element >= 0 to end of row /* int j = arr[i]; j <= sum; j++ */
row[j] += row[j-element]
return last element of row
TL;DR：请注意，在 2D 递归中，在计算table[i]条目时，您只使用table[i][...]和table[i - 1][...]。这应该会给您一个提示，只存储上一行和当前行，并引导您将空间减少到 1D 数组。
首先，考虑一个更简单的递归来找到第 N 个斐波那契数，我们将 O(N( 空间减少到 O(1( 空间：
对于复发F(n) = F(n - 1) + F(n - 2)
F[0] = 0
F[1] = 1
for(int i = 2; i <= N; i++) {
F[i] = F[i - 1] + F[i - 2]
}
return F[N]
在这里，我们看到我们只使用递归的最后2个值，并且不需要整个数组来存储所有值。
F0 = 0
F1 = 1
Fn = 1
for(int i = 2; i <= N; i++) {
Fn = F0 + F1
F0 = F1
F1 = Fn
}
return Fn
我们现在对您的问题进行类似的简化，只是在一个更高的维度上。以您的 2D 版本为例，我们将其修改为仅存储 2 行table[i - 1](如tablePrev(和table[i](如tableI(并保持更新。
tablePrev = // Initialised to the 0th row
// All I did was replace table[i - 1][...] with tablePrev[...],
// and table[i][...] with tableI[...]
for (int i = 1; i < arr.length; i++) {
tableI = tablePrev
for (int j = 1; j <= sum; j++) {
int sumWithI = j - arr[i-1] < 0 ? 0 : tableI[j - arr[i-1]];
int sumWithoutI = tablePrev[j];
tableI[j] = sumWithI + sumWithoutI;
}
tablePrev = tableI
}
就是这样。我们已将空间缩减为一维数组 - 但我们使用的是两个数组。对于这个特定的问题，现在很容易看出(由于tableI更新的性质(你甚至不需要tablePrev，可以简单地重用tableI，到达你在问题中提供的最终一维解决方案。
一维数组的解决方案只是重用您保存在单独行中的空间。这是可能的，因为不再使用这些"较旧"的行。
以代码中的以下语句为例：
int sumWithoutI = table[i - 1][j];
您可以验证这是最后一次读取该值。下次从表中读取值时，它将具有更大的i值，或者 - 如果相同 -j的值更大。因此，有空间将所有行"折叠"在一起，并用真正属于下一个i值(行(的新值覆盖数组值。