题解 | #填充数组#

填充数组

http://www.nowcoder.com/practice/3e34d9ed0bbc4db68b6fbca20a62926d

题意理解

给我们一个数组a，由自然数组成，以及一个最大值k。我们要把所有的0换成1~k中的某个值（可以重复），保持数组是递增的（这里的递增不是单调的）。问一共有多少种方法。

方法一

暴力枚举（会超时）
最简单且容易想到的方法就是列举出数组所有可能的取值，再判断是否满足递增，如果满足，种数加1。这里使用深度优先搜索，当前位置为0时，枚举所有可能的取值并递归；当前位置非0时跳过。边界条件为递归到最后一位且满足题目要求，此时种数加1。注意在递归时要判断是否满足 $a [i - 1] < = a [i]$ 。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param k int整型 
     * @return int整型
     */

    int dfs(vector<int>& a, int k, int index)
    {
        if (index==a.size()) return 1;
        int ans = 0;
        //处理当前位置为0的情况
        if (!a[index])
        {
            //注意可能的取值范围
            int begin = 1;
            if (index) begin = a[index-1];
            for (int i=begin;i<=k;i++)
            {
                a[index] = i;
                ans = (ans + dfs(a,k,index+1))%1000000007;
                a[index] = 0;
            }
        }
        else
        {
            //判断是否满足递增
            if ((index) && a[index-1]>a[index]) return 0;
            else return dfs(a,k,index+1);
        }
        return ans;
    }
    
    int FillArray(vector<int>& a, int k) {
        // write code here
        return dfs(a,k,0);
    }
};

时间复杂度： $O (k^{N})$ 。每一位有k种可能，一共有N位。
空间复杂度： $O (N)$ 。递归的深度不会超过数组的长度N。

方法二

动态规划
输入的数组已经满足了：除0以外的值都是递增的。我们将数组a视为被非0的数分隔为若干段，每段为连续的1个或多个0。可以发现，每一段的取值之间是互不干扰的。因此，最终的种数为每一段的种数的乘积。而且计算种数的时候，可以不考虑数值的具体大小，一律使用从1到m，m为这一段0的个数。

对于每一段，我们要做的是用i个数填满j个位置，且满足数组递增，用dp[j][i]。填j个位置，可以考虑先把最后一位填b，那么就是用1~b填j-1位。那么状态转移方程为：
$dp[j][i]=\sum_{b=1}^i dp[j-1][b] = dp[j-1][i] + dp[j][i-1]$

边界的话， $d p [1] [i] = i$ ; $d p [j] [1] = 1$ 。

dp的示意图如下： alt

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int dp[1001][1001];
    void GetSortNumber(int x,int y)
    {
        dp[1][1] = 1;
        for (int i=1;i<=x;i++) dp[1][i] = i;
        for (int i=1;i<=y;i++) dp[i][1] = 1;
        for (int i=2;i<=y;i++)
        {
            for (int j=2;j<=x;j++)
            {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
            }
        }
    }
    
    int FillArray(vector<int>& a, int k) {
        // write code here
        vector<int> s;
        //把所有dp求好，后面直接调用
        GetSortNumber(k,a.size());
        for (int i=0;i<a.size();i++)
        {
            if (a[i]==0)
            {
                int minm,maxm,count=1;
                if (i==0) minm = 1;
                else minm = a[i-1];
                while ((i+1)<a.size() && a[i+1]==0)
                {
                    count++;
                    i++;
                }
                if ((i+1)==a.size())  maxm = k;
                else maxm = a[i+1];
                //计算可以取值的范围（个数）
                int num = maxm - minm + 1;
                s.push_back(dp[count][num]);
            }
        }
        int ans = 1;
        for (int i=0;i<s.size();i++)
            ans = ((long long)ans * s[i]) % 1000000007;
        return ans;
    }
};

时间复杂度： $O (N k)$ 。求解dp数组是用到了双重循环，每层分别为数组a长度N和最大值k。
空间复杂度： $O (N k)$ 。dp数组的长为k，宽为N。