找到可能的不同非递减数组的总数

Question

给出确切的编号。数组中必须存在的元素的数量 (let=r) 和数组最后一个元素的最大值 (let=n) 找到可能的不同非递减数组的总数（数组的所有元素必须 >=0 )

示例 - 如果 r=3 且 n=2，则一些可能的非递减数组为 {0,0,2},{0,0,1},{0,0,0},{1,2 ,2}等我需要没有。这些数组的可能。

我尝试使用递归和记忆来解决它，但它太慢了。

这是我的代码（ll 表示 long long）-

ll solve(ll i,ll curlevel)
{
    if(dp[i][curlevel]!=-1)
        return dp[i][curlevel];
    if(i<0)
        return dp[i][curlevel]=0;
    if(curlevel==r)
        return dp[i][curlevel]=1;
    if(curlevel>r)
        return dp[i][curlevel]=0;
    ll ans=0;
    for(ll k=i;k>=0;k--)
    {
        ans+= solve(k, curlevel+1);
    }
    return dp[i][curlevel]=ans;
}

我调用这个函数如下。

for(ll i=n;i>=0;i--)
    {
        res+=solve(i, 1);
    }

我正在寻找一种更快的方法。

Answer 1

添加部分不适用：归结为非降序允许重复的组合。对于 n，我们有 0-n 个符号（即 n+1 个符号）和 r 个长度。在 mid 和 this answer on math.stackexchange 中，我们得到一个简单的公式：

Answer 2

让我们取一些符合条件的非递减序列，并使用 0 和 1 对其进行编码。解码算法简单：

将the_value设为0
对于编码序列中的每个元素：
- 如果元素为0，则输出the_value.
- 如果元素为1，则the_value加1。

现在，我声称任何非递减序列可以用恰好r个0的序列编码（因为我们需要输出恰好r 值）和n 1s（因为我们不能超过值n），并且每个这样的编码序列都对应一个唯一的非递减序列。（编码算法和双射证明留作习题。）

因此未编码序列的数量与编码序列的数量相同。但是编码序列的数量就是从编码序列的n+r个位置选择r个位置插入0的方式的数量。因此可能性的数量是 n+r 选择 r 或 (n+r)!/(n!*r!).

这些数字增长迅速，即使是中等大小的 r 和 n，您也需要 bignum 算法来计算它们。比如n和r都是2000，那么序列的个数就是1203位的数，大约是1.66 * 10¹²⁰².

显然，尝试枚举一组如此大小的序列是徒劳的。对于 r 和 n 的小值，序列可以在每个序列的摊销时间 O(1) 中枚举，使用标准的字典顺序枚举算法，该算法采用一个序列并按字典顺序生成下一个序列:

找到序列中最右边可以变大的元素。（此时，找到序列中最右边不等于n的元素。）如果没有这个元素，则所有序列都被枚举出来。
将找到的元素推进。（在这种情况下，将元素加 1。）
将所有后续元素（如果有）设置为它们的最小可能值。（在这种情况下，将所有后续元素设置为在步骤 1 中找到的元素的新值。

找到可能的不同非递减数组的总数

Find the total number of distinct Non decreasing arrays possible

algorithm

math

dynamic-programming