Super easy to understand Java DP with ArrayList[ ] solution


  • 0
    public class Solution {
        public boolean canCross(int[] stones) {
            if (stones[1] > 1) return false;
            int n = stones.length;
            ArrayList<Integer>[] steps = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                steps[i] = new ArrayList();
            }
            steps[1].add(1);
            for (int i = 2; i < n; i++) {
                for (int j = i - 1; j >= 1; j--) {
                    int curStep = stones[i] - stones[j];
                    if (!steps[j].isEmpty() && (steps[j].contains(curStep) || steps[j].contains(curStep + 1) || steps[j].contains(curStep - 1))) {
                        steps[i].add(curStep);
                    } else if (!steps[j].isEmpty() && steps[j].get(steps[j].size() - 1) < curStep) {
                        break;
                    }
                }
            }
            return !steps[n-1].isEmpty();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.