题解 | #填充数组#

对每一段零，做动态规划，看有多少方案，最后把所有方案数相乘

例如00035这个数组

以下是声明的一个3*3的数组，横坐标是可以填入的数，纵坐标是0的个数

1 1 1（第一个位置可以填1、2、3）

3 2 1（当一空填1时，二空有1、2、3三种填法；一空填2，二空有2、3两种填法；一空填3，二空有3一种填法）

6 3 1（第三空以此类推）

于是这一段的方案数为6+3+1=10种

因为只有这一段0

所以结果就是10种方案

public class Solution {
    public int FillArray (int[] a, int k) {
        long answer = 1;
        
        int index = 0;
        while(index < a.length) {
        	int zero_num = 0;
    		int min = 1;
    		int max = k;
    		if(index-1>=0)
    			min = a[index-1];
        	if(a[index] == 0) {
        		while(a[index] == 0) {
        			zero_num++;
            		index++;
            		if(index >= a.length)
            			break;
        		}
        		if(index < a.length)
        			max = a[index];
        		int[] list = new int[max-min+1];
        		for (int i = 0; i < list.length; i++) {
					list[i] = 1;
				}
        		for (int i = 1; i < zero_num; i++) {
					for (int j = 0; j < list.length; j++) {
						for (int j2 = j+1; j2 < list.length; j2++) {
							list[j] = (list[j]+list[j2]) % (int)(Math.pow(10, 9)+7);
						}
					}
				}
        		int sum = 0;
        		for (int i = 0; i < list.length; i++) {
					sum = (sum+list[i]) % (int)(Math.pow(10, 9)+7);
				}
        		answer = (answer*sum) % (int)(Math.pow(10, 9)+7);
        	}else {
				index++;
			}
        }
        
        return (int)answer;
    }
}