使用1到k的范围找到求和总值的方法数量 [英] Find the number of ways to find the total sum value using the range 1 to k

问题描述

给出一个总数，我需要计算表示1到k(含)之间总数的方式.

Given a number as total, I need to calculate the number of ways to represent the total between 1 and k(inclusive).

例如:total = 5且k = 3，即(1到3)，否.的方式= 5，不同的方式是:

For example: total=5 and k=3 ie (1 to 3), no. of ways = 5, the different ways are:

[1+1+1+1+1]
[1+1+1+2]
[1+2+2]
[1+1+3]
[2+3]

我的代码产生6而不是5.有人可以帮助我解决此问题吗?

My code produces 6 instead of 5. Can anyone help me to solve this problem:

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];
}

推荐答案

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

You can solve it using recursion as follows:

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

如果您只想找到计数，就可以进一步缩短代码，如下所示:

If you are interested in just finding the count, you can shorten the code further as follows:

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

这篇关于使用1到k的范围找到求和总值的方法数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！