填充数组

题意

给定一个数组，把其中为0的位置填上1~k, 求能让数组最终是单调上升的方案数

方法

枚举每个位置的值(TLE)

分析

我们直接对每个位置进行枚举，并在枚举过程中判断是否合法

这样每次一个合法的方案计数+1

最终这个方案数就是要求的答案

代码

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;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int FillArray(vector<int>& a, int k) {
        return dfs(a,0,k);
    }
};

复杂度分析

时间复杂度: 最坏情况是尝试了所有方案，所以总时间复杂度为$O(k^n)O(k^n)$

空间复杂度: 主要和递归深度相关，递归深度不超过数组长度，所以空间复杂度为$O(n)O(n)$

数学

分析

对于一串连续的零，限制它的填写仅与它两头的非零值相关

其关键要素是有多长和值的范围有几个,

$f(i,j)f(i,j)$表示长度为$ii$，值范围有$jj$个的方案数

$f(1,j)=jf(1,j)\; =\; j$

$f(i,1)=1f(i,1)\; =\; 1$

状态转移考虑第一个的取法，分别取1~j,剩余的取值范围变为j~1,所以

$f(i,j)=f(i-1,j)+f(i-1,j-1)+f(i-1,j-2)+\cdots +f(i-1,1)f(i,j)\; =\; f(i-1,j)\; +\; f(i-1,j-1)\; +\; f(i-1,j-2)\; +\; \backslash cdots\; +\; f(i-1,1)$

即是

$f(i,j)=f(i-1,j)+f(i,j-1)f(i,j)\; =\; f(i-1,j)\; +\; f(i,j-1)$

也就是组合数，本题的数据范围较小，可以直接对组合数进行预计算，如果更大范围可以考虑 阶乘和乘法模逆元来实现

样例

以样例数据[0,4,5],6为例

需要的值是1个位置，值可选的是4个，所以就是f[1][4]

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int FillArray(vector<int>& a, int k) {
        // f[i][j] , 长度为i,值个数为j
        vector<vector<int>>f = vector<vector<int>>(a.size()+1,vector<int>(k+1,0)); // 初始化表
        for(int i = 1 ;i<=k;i++){ // 边界初始化
            f[1][i] = i;
        }
        for(int i = 1 ;i<=a.size();i++){ // 边界初始化
            f[i][1] = 1;
        }
        for(int i = 2;i<=a.size();i++){
            for(int j = 2;j<=k;j++){
                f[i][j] = f[i-1][j] + f[i][j-1]; // 递推关系
                f[i][j] %= 1000000007;
            }
        }
        a.push_back(k); // 减少if 方便运算
        int l = -1; // 上一个不为零的位置
        long long ans = 1;
        for(int i = 0;i<a.size();i++){
            if(a[i] == 0)continue;
            if(i-l > 1){
                ans = (ans*f[i-l-1][a[i]-(l == -1?1:a[l])+1]) % 1000000007; // f[长度][值个数]
            }
            l = i;
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 主要消耗在辅助的f的计算，所以总时间复杂度为$O(kn)O(kn)$

空间复杂度: 主要和保存的f相关，所以空间复杂度为$O(kn)O(kn)$