java - 计算达到分数的方法数量

Question

我正在执行一项任务，现在我有一个数字，我想知道使用 2,3,6 使用加法有多少种方法可以达到这个数字，并且我可以使用一个数字尽可能多的次数。

第一个示例:

Given number is 6
There are 3 ways to reach to this number:
2 +2 + 2 = 2*3
3 + 3 = 3*2
6

第二个示例:

Given number is 5
There are 2 ways to reach to this number:
2+3
3+2 (order matters here)

我在this link的帮助下想出了下面的代码:

static int count(int n) {
    // table[i] will store count of solutions for
    // value i.
    int table[] = new int[n + 1], i;

    // Base case (If given value is 0)
    table[0] = 1;

    // One by one consider given 3
    // moves and update the table[]
    // values after the index greater
    // than or equal to the value of
    // the picked move
    for (i = 2; i <= n; i++)
        table[i] += table[i - 2];
    for (i = 3; i <= n; i++)
        table[i] += table[i - 3];
    for (i = 6; i <= n; i++)
        table[i] += table[i - 6];

    return table[n];
}

此代码仅适用于第一个示例，但不适用于第二个示例，因为程序返回 1 而不是 2。

如何解决这个问题？

Answer 1

问题是您错过了诸如 2+6+2 之类的组合(其中较小的数字出现在较大的数字之后)，因为您运行(例如)table[10] += table[10-2 ] 之前 table[8] += table[8-6]，因此前者不考虑后者的结果。

要解决这个问题，请更改以下内容:

    for (i = 2; i <= n; i++)
        table[i] += table[i - 2];
    for (i = 3; i <= n; i++)
        table[i] += table[i - 3];
    for (i = 6; i <= n; i++)
        table[i] += table[i - 6];

对此:

    for (i = 1; i <= n; i++) {
        if (i >= 2) {
            table[i] += table[i - 2];
        }
        if (i >= 3) {
            table[i] += table[i - 3];
        }
        if (i >= 6) {
            table[i] += table[i - 6];
        }
    }

以便您处理例如table[10] 仅在您完全处理后，例如表[8]。