想知道rec函数的时间复杂度

Question

我尝试解决leetcode问题q.select网格中得分最高的单元格。但它给出了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;



    }

}

Answer 1

请注意，有 10¹⁰ 种方法可以从 10 x 10 网格的每一行中选择一个数字。这清楚地表明蛮力太慢了。

相反，观察到行数非常小——最多只有 10 行。因此，我们可以采用动态编程，其中状态是实际使用的行（表示为位掩码）。现在只需要避免选择重复的数字，这可以通过首先查找每个数字出现在哪些行，然后在一次传递中为每个可能的整数更新所有最佳答案（与背包问题类似）来实现。

时间复杂度为

O(RC * 2^R)

，其中

R

是行数，

C

是列数，足够快了。

public int maxScore(List<List<Integer>> grid) {
    var maxScore = new int[1 << 10];
    List<Integer>[] occurrences = new List[101];
    Arrays.setAll(occurrences, i -> new ArrayList<>());
    for (int row = 0; row < grid.size(); row++)
        for (int val : grid.get(row))
            occurrences[val].add(row);
    for (int i = 1; i < occurrences.length; i++)
        if (!occurrences[i].isEmpty())
            for (int j = maxScore.length - 1; j > 0; j--)
                for (int r : occurrences[i])
                    if ((j >> r & 1) != 0)
                        maxScore[j] = Math.max(maxScore[j], maxScore[j ^ (1 << r)] + i);
    return maxScore[maxScore.length - 1];
}