题意：


方法一：
动态规划

思路：
        dp[i][j]表示填充i个数，取值个数是j的方案数。
        状态转移方程如下：
            

        因为本题涉及多段连续的 0 ，因此，计算每一段连续 0 的方案，并且累乘即可。


#define ll long long

class Solution {
public:
    const int MOD=1e9+7;
    ll dp[1005][1005]={0};//dp[i][j]表示填充i个数，取值个数是j的方案数
    int FillArray(vector<int>& a, int k) {
        ll res=1;
        int n=a.size();
        //初始化
        for(int i=1;i<=k;i++){
            dp[1][i]=i;
        }
        for(int i=2;i<=n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;//状态转移方程
            }
        }
        
        int i=0;
        while(i<n){//计算每一段的方案数，累乘
            
            while(i<n&&a[i]!=0){
                i++;
            }
            if(i==n)
                break;
            int l=i;//左区间
            int x=i>0?a[i-1]:1;
            while(i<n&&a[i]==0){
                i++;
            }
            int r=i;//右区间
            int y=i<n?a[i]:k;
            res=(res*dp[r-l][y-x+1])%MOD;//累乘
        }
        return res;
    }
};


时间复杂度：
空间复杂度：

方法二：
java

思路：
        dp[i][j]表示填充i个数，取值个数是j的方案数。
        状态转移方程如下：
         
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;//状态转移方程



import java.util.*;


public class Solution {
    
    int MOD=1000000007;
    long[][] dp=new long[1005][1005];//dp[i][j]表示填充i个数，取值个数是j的方案数
    public int FillArray(int[] a, int k) {
        long res=1;
        int n=a.length;
        //初始化
        for(int i=1;i<=k;i++){
            dp[1][i]=i;
        }
        for(int i=2;i<=n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;//状态转移方程
            }
        }
        
        int i=0;
        while(i<n){//计算每一段的方案数，累乘
            
            while(i<n&&a[i]!=0){
                i++;
            }
            if(i==n)
                break;
            int l=i;//左区间
            int x=i>0?a[i-1]:1;
            while(i<n&&a[i]==0){
                i++;
            }
            int r=i;//右区间
            int y=i<n?a[i]:k;
            res=(res*dp[r-l][y-x+1])%MOD;//累乘
        }
        return (int)res;
    }
}

时间复杂度：
空间复杂度：