牛客网 NC173 填充数组 -动态规划

问题：

描述

牛妹给了牛牛一个长度为 nn 的下标从00开始的正整型数组 aa ，粗心的牛牛不小心把其中的一些数字删除了。

假如a_{i}ai被删除了，则a_{i}=0ai=0。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：

a_{0} leq a_{1} leq...leq a_{n-1}a0≤a1≤...≤an−1 且对于所有的0 leq i leq n-10≤i≤n−1满足1 leq a_{i} leq k1≤ai≤k 。

函数传入一个下标从00开始的数组 aa 和一个正整数 kk ，请返回合法的填充方案数对 10^9+7109+7取模的值,保证不存在方案数为0的数据。

示例1

输入：

[0,4,5],6

复制返回值：

4

复制说明：

所有的合法填充方案是：[1,4,5],[2,4,5],[3,4,5],[4,4,5]，共4种。

示例2

输入：

[1,0,0],3

复制返回值：

6

复制说明：

所有的合法填充方案是：[1,1,1],[1,1,2],[1,2,2],[1,2,3],[1,3,3],[1,1,3]共6种

示例3

输入：

[0,0,0,0,0,67,0,0],100

复制返回值：

746845806

复制

备注：

1 leq n,k leq 10001≤n,k≤1000

数组aa满足0 leq a_{i} leq k0≤ai≤k

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int FillArray (int[] a, int k) {

        //a[?] 方案数 = a[?-1]的方案数 * a【?】的数字 - a[?]-1的方案数 *a[?]-a[?-1]
        BigInteger aa =  getAs(a, a.length - 1, k, k, new  HashMap<String, BigInteger>());
        return aa.intValue();
    }
    //数组 当前下标
    public BigInteger getAs(int[] a, int i, int num, int nowNumber,
                            HashMap<String, BigInteger> map) {
        BigInteger res = BigInteger.valueOf(0);
        Long m = 1000000007l;
        //如果已经是最后一个了 直接返回当前方案+1
        if (i == 0 && a[i] <= nowNumber) {
            return  BigInteger.valueOf(1);
        } else {
            if (a[i - 1] > nowNumber) {
                return  BigInteger.valueOf(0);
            }
        }
        //判断当前下标是否为0如果不为0就跳过
        if (a[i] != 0) {
        //a[i] > nowNumber 说明无解直返回0  i==0 说明有1个解返回  否则 继续找
            return a[i] > nowNumber ?  BigInteger.valueOf(0) : i == 0 ?  BigInteger.valueOf(
                       1) : getAs(a, i - 1, num, a[i], map);
        }

        //如果为0并且不是最后一个，说明要根据next 现在填充的值进行递归计算
        BigInteger next = BigInteger.valueOf(0);
        BigInteger son = BigInteger.valueOf(0);
        String nextKey = String.valueOf(i - 1) + "_" + String.valueOf(nowNumber);
        String sonKey = String.valueOf(i) + "_" + String.valueOf(nowNumber - 1);

        if (map.get(nextKey) != null) {
            next = map.get(nextKey);
        } else {
            next = i == 0 ?  BigInteger.valueOf(0) : getAs( a, i - 1, num, nowNumber, map);
//记录缓存 i+nowNumber
            map.put(nextKey, next);
        }
        if (map.get(sonKey) != null) {
            son = map.get(sonKey);
        } else {
            son = nowNumber - 1 == 0 ?  BigInteger.valueOf(0) : getAs( a, i, num,
                    nowNumber - 1, map);
//记录缓存
            map.put(sonKey, son);
        }
        res = next.add(son).remainder(BigInteger.valueOf(1000000007)) ;
        return res;

    }
}