卡片、包包和钱币的递归关系理解

Question

给定一个包含 n 个整数的数组 A 和一个正整数 m (1<=m<=100)，求该数组中可被 m 整除的子集的数量。

递归关系：设 dp[i][j] 表示包含数组中第 i 个元素的元素的子集数，当除以 my m 时其元素之和得到余数 j。

dp(i,j) = dp(i-1,j) + dp(i-1,(j-a[i])%m)

但是，我无法理解 j-a[i] 部分。让我解释清楚为什么我坚持用一个例子。

[6, 7, 7] 和 m=5

假设我们在索引 0 处：这里我们只需要知道数字是否可以被 5 整除。如果没有，就知道 mod 它是什么 returns 并记住它。

dp[0][1] 应该为真，因为它留下了 1 的余数 (6%5)。

索引 1 也是如此：dp[1][2] 将为真，因为 7%5=2。我们还需要以某种方式知道记录 dp[1][3] 与添加 (6+7)%5 = 3.

一样真实

但是，在索引 2 处，我们需要知道过去的结果 dp[1][3]，以便将 dp[2][0] 标记为真，因为 (3+2)%5 是 0。

任何人都可以帮助我理解这一点，我已经为此花费了无数时间但没有太大进展。

还有一个问题是关于否定 mod 的。这个递归关系是怎么处理的？

Answer 1

要首先了解解决方案，您需要了解以下内容-

有 i 个项目的集合的子集（假设这组子集是 I）是 -

的并集

1) 包含 i-1 个项目的集合的子集。让这组子集表示为J.

2) 以及所有这些子集（步骤 1 的）与第 i 个元素的并集。让这组子集用K.

表示

示例 - 让项目为 [1, 2, 3]

现在，包含 2 个项目的集合的子集是 - {}, {1}, {2}, {1,2} 即 J.

所以，K={3}，{1,3}，{2,3}，{1,2,3}

我=J+K

现在让我们转到您的问题。

类似或者你可以调用类似移动方法dp[i][j]（或I）是dp[i-1][j]（或J) 加上 K.

K可以找到包含J中的第i个元素即dp[i-1][(j-a[i])%m]。现在，由于我们已经包含了第 i 个项目，所以我们需要添加需要总和的数字 sum - 第 i 个项目的值，因为它已经被包含在内。这就是使用 (j-a[i]).

的原因

如何获得绝对值 - 只需创建一个 returns 给定数字绝对值的函数，然后在您认为可能需要的任何地方使用它。

这是函数的代码-

int abs(int x){
     return x>0?x:-x;
}

Cards, bags and coins recurrence relation understanding