1871. Jump Game VII

 一刷 06/2022

Version #1 DP + Sliding Window Sum

一开始用了dfs + memorization, 虽然dfs可以保证是O(N)的复杂度，但是在dfs内部需要从index + minJump一直check到index + maxJump这样最高是 maxJump - minJump ~ N的复杂度就是total O(N^2) 所以会TLE

Time O(N)

Space O(N)

Runtime: 15 ms, faster than 75.05% of Java online submissions for Jump Game VII.

Memory Usage: 54.8 MB, less than 50.09% of Java online submissions for Jump Game VII.

class Solution {

    public boolean canReach(String s, int minJump, int maxJump) {

        char[] chars = s.toCharArray();

        //      |

        // "011010"

        //   ()

        // Look at the sliding window sum of index [i-maxJump, i-minJump]

        // if sum > 0, then current position can be reached

        // sum is the count of indexes that can be reached in the range

        boolean[] dp = new boolean[chars.length];

        dp[0] = true;

        int sum = 0;

        // sum range [i - maxJum, i - minJump]

        for (int i = minJump; i < chars.length; i++) {

            if (dp[i - minJump]) {

                sum++;

            }

            if (i - maxJump - 1 >= 0 && dp[i - maxJump - 1]) {

                sum--;

            }

            if (sum > 0 && chars[i] == '0') {

                dp[i] = true;

            }

        }

        return dp[chars.length - 1];

    }

    

}