题解 | #填充数组#

class Solution {
public:
    #define A 1000000007
    int FillArray(vector<int>& a, int k) {
    long long ans=1;
    int left,right;
    a.push_back(k);
    a.insert(a.begin(),1);
    bool check=0;
    for(int i=0;i<a.size();i++){
    if(a[i]==0&&!check)
    {left=i;
    check=1;}
	else if(a[i]!=0&&check){
    right=i;
    check=0;
    ans*=cal(right-left,a[right]-a[left-1]+1);
    ans%=(A);
    }
    }
    return ans%(A);
    }
    long long cal(int n,int k){
    cout<<n<<" "<<k<<endl;
    vector<vector<long long>>a(n+1,vector<long long>(k+1,1));
    for(int i=1;i<=k;i++)
    a[1][i]=i;
    for(int i=2;i<=n;i++){
    for(int j=2;j<=k;j++){
    a[i][j]=(a[i-1][j]+a[i][j-1])%A;
    }
    }
    return a[n][k]%A;
    }
};

时间复杂度：最坏情况：n+n*k

空间复杂度：n*k