Clean O(N^2) dp solution in java


  • 0
    V

    The idea is to use a boolean matrix to store the status of the stone and "units can jump forward" pair.

            // the first dimension is the index of the stone,
            // the second one is the units that the frog can jump forward from this stone
            int n = stones.length;
            boolean[][] matrix = new boolean[n][n];
            matrix[0][1] = true;
            int target = stones[n-1];
            for (int i = 1; i < n; i++) {
                for (int j = i-1; j >= 0; j--) {
                    // the maximum units the frog can jump is the length of the input array
                    if (stones[i] - stones[j] >= n)
                        break;
                    if (matrix[j][stones[i] - stones[j]]) {
                        if (target >= stones[i] + stones[i] - stones[j] - 1 && target <= stones[i] + stones[i] - stones[j] + 1)
                            return true;
                        if (stones[i] - stones[j] > 1)
                            matrix[i][stones[i] - stones[j]-1] = true;
                        matrix[i][stones[i] - stones[j]] = true;
                        if (stones[i] - stones[j] + 1 < n)
                            matrix[i][stones[i] - stones[j]+1] = true;
                    }
                }
            }
            return false;
    

Log in to reply
 

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