给定一个总数,我需要计算表示 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/