8.26腾讯音乐笔试第三题求解

        public int FillArray (int[] a, int k) {
            // write code here
            int mod = (int)(Math.pow(10, 9)+7);
            int n =a.length;
            //dp[i][j]表示第i个数选择j的方案数
            int[][] dp = new int[n][k+1];
            if(a[0]!=0){
                dp[0][a[0]]=1;
            }else{
                for(int i=1;i<=k;i++){
                    dp[0][i] = 1;
                }
            }

            for(int i=1;i<n;i++){
                if(a[i]!=0){
                    for(int j=0;j<=a[i];j++){
                        dp[i][a[i]] = (dp[i][a[i]]%mod + dp[i-1][j]%mod)%mod;
                    }
                }else{
                    for(int j=0;j<=k;j++){
                        for(int x=0;x<=j;x++){
                            dp[i][j] = (dp[i][j]%mod + dp[i-1][x]%mod)%mod;
                        }
                    }
                }
            }

            int ans = 0;
            if(a[n-1]!=0){
                ans = dp[n-1][a[n-1]];
            }else{
                for(int i=0;i<=k;i++){
                    ans = (ans%mod+dp[n-1][i]%mod)%mod;
                }
            }
            return ans;
        }