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

Question

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

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

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

这是我的代码(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

让我们采用一些符合条件的非递减序列，并使用 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) 中枚举序列，该算法采用一个序列并产生下一个字典顺序:

1. 找到序列中最右边可以变大的元素。 (在这种情况下，找到序列中最右边不等于n的元素。)如果没有这样的元素，则所有序列都已被枚举。

2. 推进已找到的元素。 (在这种情况下，将元素加 1。)

3. 将所有后续元素(如果有)设置为它们的最小可能值。 (在这种情况下，将所有后续元素设置为在步骤 1 中找到的元素的新值。