函数查找使用最多m个部分拆分n个对象的方法的数量

Question

我正在使用递归来解决这个问题。从纸面上看，我的答案应该是可行的，所以我把代码弄错了。然而，我不知道问题出在哪里。

public class Partition {
    public static void main(String[] args) {
        System.out.println(part(6,4));
    }

    public static int part(int n, int m) {
        if (n==0) {
            return 1;
        }
        else if(m == 0 || n<0) {
            return 0;
        }
        else {
            return part(n-m, m) + part(n, m);
        }
    }
}

Answer 1

我不确定你想做什么，但如果要计算组合，应该如下所示：

public static int part(int n, int m) {
    if(m>n) { //This prevent a wrong input from the user
        return part(m, n);
    } else if (m==0 || m==n) { //This is your base case
        return 1;
    } else if(m < 0 || n<0) { //this should not happened, but you never know
        return 0;
    }  else { //this is where you're making mistake(s)
        //I don't know if I'm using the formula you are looking for
        //But if not, make sure yours do not use part(n, m) otherwise it will run forever
        return part(n-1, m) + part(n-1, m-1);
    }
}

Answer 2

您只需减少m，问题就会返回9，如您所示。

public static int part (int n, int m) {
    if (n == 0) {
        return 1;
    } else if (m == 0 || n < 0) {
        return 0;
    } else {
        return part(n - m, m--) + part(n, m);
    }
}