递归问题 - 给定数组 n 和数字 k

Question

给定一个数组大小 n 和一个正数 max（max 表示我们可以用来放置在数组中的数字的范围）。

我想计算我可以在数组中放置多少个排序数字组合。

例如 ：

如果n = 3, max = 2.（我们可以使用的唯一数字是 1/2，因为最大值是 2）所以排序数组有 4 种组合

 1. {1,1,1}
 2. {1,1,2}
 3. {1,2,2}
 4. {2,2,2}

我写了一些代码并成功通过了这个特定的例子，但max > 2没有返回正确答案的任何其他例子。

我发现的问题是当递归到达最后一个索引时，它不会尝试第三个数字，它只是折回。

我的代码：

private static int howManySorted(int n, int max, int index, int numToMax, int prevNum) {        
    // If the value is bigger then max return 0
    if(numToMax > max) {
        return 0;
    }
    if (numToMax < prevNum) {
        return 0;
    }
    //If Index reached the end of the array return 1
    if(index == n) {
        return 1;
    }

    int sortTwo =  howManySorted(n, max, index+1, numToMax, numToMax);
    int sortOne =  howManySorted(n, max, index+1, numToMax+1, numToMax);
    return ((sortOne+sortTwo));
}

public static int howManySorted(int n, int max) {
    return howManySorted(n, max, 0, 1, 0);
}

Answer 1

我认为你需要更改你的两个递归调用（这就是为什么它只达到值 2）并执行与你的max参数一样多的调用：

private static int howManySorted(int n, int max, int index, int numToMax, int prevNum) {
    // If the value is bigger then max return 0
    if (numToMax > max) {
        return 0;
    }
    if (numToMax < prevNum) {
        return 0;
    }
    //If Index reached the end of the array return 1
    if (index == n) {
        return 1;
    }

    int result = 0;
    for (int i = 0; i < max; i++)
        result += howManySorted(n, max, index + 1, numToMax + i, numToMax);

    return result;
}