给定一个总数,我需要计算表示 1 和 k(含)之间总数的方法数。
例如:total=5 and k=3 即(1 到 3),没有。方式= 5,不同的方式是:

[1+1+1+1+1]
[1+1+1+2]
[1+2+2]
[1+1+3]
[2+3]
我的代码生成 6 而不是 5。谁能帮我解决这个问题:
public static int ways(int total, int k) {
    int C[][] = new int[n + 1][k + 1];
    int i, j;
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= Math.min(k, i); j++) {
            if (j == 0 || j == i) {
                C[i][j] = 1;
            } else {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j - 1];
            }
        }
    }
    return C[n][k];
}

最佳答案

您可以使用递归解决它,如下所示:

public class IntegerPartition {
    static int count=0;
    public static void partition(int total, int k) {
        partition(total, k, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            System.out.println(prefix);
            count++;
            return;
        }
        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n - i, i, prefix + " " + i);
        }
    }

    public static void main(String[] args) {
        partition(5,3);
        System.out.println("Count: "+count);
    }
}

输出:
 3 2
 3 1 1
 2 2 1
 2 1 1 1
 1 1 1 1 1
Count: 5

如果您只想找到计数,可以进一步缩短代码,如下所示:
public class IntegerPartition {
    static int count=0;
    public static void partition(int n, int max) {
        if (n == 0) {
            count++;
            return;
        }
        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n - i, i);
        }
    }
    public static void main(String[] args) {
        partition(5,3);
        System.out.println("Count: "+count);
    }
}

输出:
Count: 5

关于java - 使用范围 1 到 k 查找求总和值的方法数,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/58486802/

10-11 22:29
查看更多