如何从x个连续数字中递归地计算可能增加序列的数量？

Question

设整数x为数字组合的长度，并设有从1到max的连续整数范围。序列必须是不递减的（序列一般是递增的，但可能有相同的连续数字）。给定x和max有多少这样的序列是可能的？

例如，对于x=3，max=2，有4个可能的序列：

1,1,1

1,1,2

1,2,2

2,2,2

我想到了以下递归方法：

public static int howManySorted(int n, int max, int len, int i) {
        if(len > n || i > max) {
            return 0;
        }

        if(len == n && i == max) {
            return 1;
        }

        return howManySorted(n, max, len + 1, i + 1) +
                howManySorted(n, max, len + 1, i) +
                howManySorted(n, max, len, i + 1);
}

>

howManySorted（n，max，len 1，i）是指序列长度增加1，而下一个数字与前一个数字相同1的情况。

我确实意识到我的递归公式有问题，因为在这样的序列中，相邻数字之间的差值最多为1。因此，我决定添加另一个调用howManySorted（n，max，len，I 1），这将补偿此类情况，但这仍然不会产生预期的结果。我做错了什么？

我从main中调用这个方法，如下howManySorted（n， max，1,1）。

Answer 1

假设len=10和max=5。

请注意，由于我们对实际解不感兴趣，只对计数感兴趣，因此范围2-5的结果与范围1-4的结果相同。

对于第一个数字，我们可以选择数字1-5，然后：

1. 递归调用，长度为9，将数字范围限制为1-5，即最大值为5

汇总递归调用返回的计数。这是这次通话的结果。

当len=1时，存在最大值，因此返回最大值作为计数。

当最大值=1时，无论长度如何，只有一个解决方案，因此返回1作为计数。

我将把实际的编码留给你。