Don’t look back, go forward?

It is true that for a positive attitude to life, we should don’t look back, go forward. However, for dynamic programming, we can try this way:

If we cannot go forward, look backward.

As for most problems, we can either look forward or look backward. Sometimes, both approaches work. Sometimes, one works better than the other one.

We can exactly use this strategy to solve the following problem.

1871. Jump Game VII

This is the third problem of LC weekly contest (May 22, 2021). If we look forward, for each 0, we have a region which are reachable, we have to update that region. This process will make the algorithm have the complexity of O(n²), hence it will get TLE.

Instead of looking forward, we can look backward instead. As if we look backward, we can use a prefix sum to improve the check whether we have any reachable points with the complexity of O(1).

Think about the following example

   L              R
0000000010000001000000

In order to check whether we have 1 between L and R, we only need check the prefix sum[R]-prefix sum[L-1] > 0. This checking only have the complexity of O(1). So the overall time complexity will be reduced from O(n²) to O(n)

Reference Code

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        const int n = s.size();
        vector<bool> reachable(n+1, false);
        vector<int> prefixsum(n+1, 0);
        reachable[1] = true;
        prefixsum[1] = 1;
        // use 1 based index
        for (int i = 1; i <=n; ++i) 
        {
            if (s[i-1] == '1') 
            {
                prefixsum[i] = prefixsum[i-1];
                continue;
            }
            // look back to see whether we have any reachable points in the region [l, r], if so, the point i can be reachable.
            // See if any points reachable in [l, r], we can check the prefix sum. If we have any true in [l, R], the region sum 
            // should be greater than 0.
            int l = i - maxJump, r = i - minJump;
            // if r is less than 1, it means this zero is unreachable.
            if (r >= 1) {
                 l = max(1, l);
                 reachable[i] = prefixsum[r] -  prefixsum[l-1] > 0;
            }
            prefixsum[i] = prefixsum[i-1] + reachable[i];
        }
        return reachable[n];
    }
};

Reference

[1]https://youtu.be/1UjN4cXyL34