求问一道亚麻高频题 青蛙跳 的复杂度

    // dfs + memorization
    public boolean canCross(int[] stones) {
        Map<Integer, Integer> map = new HashMap<>();
        Set<String> bad = new HashSet<>();
        for (int stone : stones) {
            map.put(stone, map.getOrDefault(stone, 0) + 1);
        }
        return dfs(0, 1, stones[stones.length - 1], map, bad);
    }
   
    private boolean dfs(int pos, int jump, int target, Map<Integer, Integer> map, Set<String> bad) {
        String key = "pos" + pos + "jump" + jump;
        if (bad.contains(key)) return false;
        int nextPos = pos + jump;
        if (nextPos == target) return true;
        if (!map.containsKey(nextPos) || map.get(nextPos) == 0) {
            bad.add(key);
            return false;
        }
        
        for (int i = -1; i <= 1; i++) {
            if (jump + i > 0) {
                map.put(nextPos, map.get(nextPos) - 1);
                if (dfs(nextPos, jump + i, target, map, bad)) {
                    return true;
                }
                map.put(nextPos, map.get(nextPos) + 1);
            }
        }
        
        bad.add(key);
        return false;
    }

我用的解法是dfs+memo，第一个map算记录每个元素出现的次数，第二个map记录坏的情况，就是在这个pos，跳jump次，是没有到达最后的， 但是不知道应该怎么分析时间复杂度，求大神指点一下，感觉应该是比O(n)大，比O(3^n)小

有大神说是O(n^2), 但是不知道是怎么得出来的