😀403 frog jump （记忆化搜索）

https://leetcode.com/problems/frog-jump/

终于遇到一道记忆化搜索的题了，题意很绕，大概就是你跳到这一步用了k步，你的下一跳就只能是k + 1, k - 1, k步，然后第一步跳一定是跳1步，所以用dfs可以很方便的解出来，dfs的对象是站在跳到当前位置用了k步能不能跳到终点，然后用记忆化减少时间复杂度，这样已经dfs过的position + steps组合就不用再看了

class Solution {
    Map<String, Boolean> map = new HashMap<>();
    public boolean canCross(int[] stones) {
        if (stones.length <= 1) return true;
        if (stones[1] != 1) return false;
        return dfs(stones, 1, 1);
    }
    private boolean dfs(int[] stones, int index, int steps) {
        if (index == stones.length - 1) {
            return true;
        }
        if (map.containsKey(index + " " + steps)) {
            return map.get(index + " " + steps);
        }
        boolean flag = false;
        
        for (int i = index + 1; i < stones.length; i++) {
            int curSteps = stones[i] - stones[index];
            if (steps == curSteps) {
                flag = flag || dfs(stones, i, curSteps);
            }
            if (steps + 1 == curSteps) {
                flag = flag || dfs(stones, i, curSteps);
            }
            if (steps - 1 == curSteps) {
                flag = flag || dfs(stones, i, curSteps);
            }
        }
        map.put(index + " " + steps, flag);
        return flag;
    }
}