image.png

    1. class Solution {
    2.     public boolean canCross(int[] stones) {
    3.         // 回溯法递归
    4.         int  n = stones.length;
    5.         Map<Integer, Boolean> map = new HashMap<>();
    6.         return DFS(stones, 0, 0, n, map);
    7.     }
    8.     /**
    9.     *  index: 表示现在所处的索引
    10.     *  k: 表示上一步跳跃了几个单元格
    11.     *  n: 表示数组长度
    12.     *  map: 表示经历过的状态
    13.     **/
    14.     private boolean DFS(int[] stones, int index, int k, int n, Map<Integer, Boolean> map) {
    15.         // 递归终止条件
    16.         // System.out.println("index:" + index + "  k:" + k);
    17.         if (index == n - 1) {
    18.             return true;
    19.         }
    20.         int key = index * 1000 + k;
    21.         if (map.containsKey(key)) {
    22.             return false;
    23.         } else {
    24.             map.put(key, true);
    25.         }
    26.         for (int i = index + 1; i < n; i++) {
    27.             int gap = stones[i] - stones[index];
    28.             if (k - 1 <= gap && gap <= k + 1) {
    29.                 if (DFS(stones, i, gap, n, map)) {
    30.                     return true;
    31.                 }
    32.             } else if (gap > k + 1) {
    33.                 break;
    34.             } else {
    35.                 continue;
    36.             }
    37.         }
    38.         return false;
    39.     }
    40. }