java - 这个dfs算法的时间复杂度是多少

Question

问题陈述:给定一个非负整数数组，您最初位于数组的第一个索引处。//一个leetcode问题

我只是对计算它的复杂性感到困惑。 tike 复杂度是多少？您能否推荐任何教授 tike 复杂度计算的书籍或教程

   class Solution {
    public boolean canJump(int[] nums,int sum,boolean isreach[]) {
        if(sum == nums.length-1){
            return true;
        }
        if(sum >= nums.length){
            return false;
        }
        if(isreach[sum]) return true;
        int j = nums[sum];
        int k = 1;
        boolean check = false;
        while( k <= j && sum + k < nums.length ){       
           check = check || canJump(nums, sum+k,isreach);
           if(check) {isreach[sum] = check; return true;}
           k++;
        }
        return false;
    }
    public boolean canJump(int[] nums) {
        boolean isreach[] = new boolean[nums.length];
        return canJump(nums,0,isreach);
    }
 }

我认为是n^2

Answer 1

首先，这不是广度优先搜索算法。我很确定您所指的问题是 Jump Game problem from LeetCode ，其最优解是使用动态规划，而不是广度优先搜索。

您上面介绍的算法只是一种自上而下的动态规划算法，它会记住它找到的较小子问题的解决方案。该算法的运行时间为 O(N)(其中 N 是您想要达到的 sum 值)，因为最多有 >N 个您将访问的不同州。