题解 | #填充数组#

填充数组

题目描述

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

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

$a_0\le a_1\le \mathrm{.}\mathrm{.}\mathrm{.}\le a_{n-1}a\_\{0\}\; \backslash leq\; a\_\{1\}\; \backslash leq...\backslash leq\; a\_\{n-1\}$且对于所有的$0\le i\le n-10\; \backslash leq\; i\; \backslash leq\; n-1$满足$1\le a_i\le k1\; \backslash leq\; a\_\{i\}\; \backslash leq\; k$。

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

方法一：枚举法

解题思路

对于本题目的求解，直接对每个位置进行枚举，并在枚举过程中判断是否合法，最后返回结果。

解题代码

class Solution {
public:
    int dfs(vector<int>& a,int idx,int k)
    { // 数组，当前尝试下标，值上限
        if(idx == a.size())return 1; // 枚举到数组结尾
        if(a[idx] != 0)
        { // 已经填写了
            if(idx != 0 && a[idx] < a[idx-1])return 0; // 非递增
            return dfs(a,idx+1,k); // 下一个位置
        }
        int ans = 0;
        for(int i = (idx == 0?1:a[idx-1]);i<=k;i++)
        { // 枚举
            a[idx] = i;
            ans = (ans+dfs(a,idx+1,k))%1000000007; // 下一个位置
            a[idx] = 0; // 清理
        }
        return ans;
    }
    int FillArray(vector<int>& a, int k) {
        return dfs(a,0,k);
    }
};

复杂度分析

时间复杂度：最坏的情况是枚举完所有方案，因此时间复杂度为$O(k^n)O(k^n)$。

空间复杂度：使用递归，且递归深度不超过数组长度，因此空间复杂度为$O(n)O(n)$

方法二：动态规划的方法

解题思路

本题也可以用动态规划的方法，dp[i][j]表示填充i个数，取值个数是j的方案数。且根据问题的描述，填充i个数，取值个数是j的方案数等于填充i-1个数，取值个数为j的方案数加上填充i个数，取值个数是j-1的方案数，因此有如下状态转移方程：

$dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]\; =\; dp[i-1][j]\; +\; dp[i][j-1]$

解题代码

class Solution {
public:
    const int MOD=1e9+7;
    long long dp[1005][1005]={0};//dp[i][j]表示填充i个数，取值个数是j的方案数
    int FillArray(vector<int>& a, int k)
    {
        long long 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;//返回结果
    }
};

复杂度分析

时间复杂度：两层循环，因此时间复杂度为$O(n\ast k)O(n*k)$，其中n为数组的大小，k为取值个数。

空间复杂度：使用二维dp数组，因此空间复杂度为$O(n\ast k)O(n*k)$，其中n为数组的大小，k为取值个数。