LeetCode网格选分问题递归解法超时：求rec函数时间复杂度及分析方法

题目描述 #

给定一个由正整数组成的二维矩阵grid，需从矩阵中选择一个或多个单元格，满足以下条件：

• 任意两个选中单元格不在同一行；
• 选中单元格的值互不相同；
  得分是选中单元格的值之和，返回能获得的最大得分。

约束条件 #

• 1 ≤ grid.length, grid[i].length ≤ 10
• 1 ≤ grid[i][j] ≤ 100

问题背景 #

我编写的递归解法出现超时（TLE），但网格最大仅为10×10。我认为rec函数的时间复杂度是指数级的，想知道该rec函数的时间复杂度，以及如何快速分析递归的时间复杂度。整体时间复杂度大概为n×m×(rec函数的时间复杂度)。

附原递归代码：

class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int ans=0;
        boolean[] hash=new boolean[101];
        for(int i=0;i<grid.size();i++){
            List<Integer> li=grid.get(i);
            for(int j=0;j<li.size();j++){
                int num=li.get(j);
                hash[num]=true;
                ans=Math.max(ans,num+rec(grid,i+1,hash,0));
                hash[num]=false;
            }
        }
        return ans;
    }
    public int rec(List<List<Integer>> grid,int i,boolean[] hash,int ans){
        if(i==grid.size()){
            return ans;
        }
        int sum=ans;
        List<Integer> li=grid.get(i);
        for(int j=0;j<li.size();j++){
            int num=li.get(j);
            hash[num]=true;
            sum=Math.max(sum,rec(grid,i+1,hash,ans+num));
            hash[num]=false;
        }
        return sum;
    }
}

递归函数时间复杂度分析 #

1. rec函数的时间复杂度 #

设网格有n行，每行平均有m个元素。rec函数从第i行开始处理，每一行会产生m+1个分支：

• 1个不选当前行任何元素的分支；
• m个选当前行某一元素的分支；

递归深度为n（从当前行到最后一行），因此时间复杂度为O((m+1)^n)，属于指数级。当n=10、m=10时，11^10≈2.59×10^10，操作量远超时间限制，这是超时的核心原因。

另外原代码未判断hash[num]是否已被标记，存在逻辑错误（允许选中重复值），同时因无记忆化处理，相同状态会被重复计算，进一步加剧时间消耗。

2. 快速分析递归时间复杂度的方法 #

• 统计分支数：确定每一层递归会产生多少独立子问题，比如本题中每行有m+1个分支；
• 计算递归深度：递归的最大调用层数，本题为n；
• 推导复杂度：指数级复杂度通常为「分支数^递归深度」，多项式复杂度则是「分支数×递归深度」或更低阶的组合。

优化思路 #

利用行数量少（最多10行）的特点，采用状态压缩动态规划：

• 用n位二进制数mask表示已选中的行（第i位为1代表第i行已被使用）；
• 定义dp[mask]为选中mask对应行时的最大得分；
• 遍历每个数值，对每个mask，若该数值所在行未被选中，则更新dp[mask | 行掩码] = max(dp[mask | 行掩码], dp[mask] + 数值)；

该方法的状态数仅为2^10=1024，时间复杂度为O(D×2^n)（D为不同数值的数量，最多100），操作量约10万次，完全符合时间要求。

内容的提问来源于stack exchange，提问作者Harry