时间戳

首页 > 解决方案 > 计算达到分数的方法数

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

问题描述

我正在处理一个我现在有一个数字的任务我想知道有多少种方法可以使用 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)

在此链接的帮助下，我提出了以下代码：

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。

如何解决这个问题？

标签： javaalgorithm

解决方案

问题是您错过了诸如 2+6+2 之类的组合（其中较小的数字出现在较大的数字之后），因为您（例如）运行table[10] += table[10-2] before 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]只有在完全处理完 eg 后才能处理 eg table[8]。

推荐阅读