Evolve from brute force to optimal


  • 1

    If we cannot come up with the optimal solution at first thought, we may think about the brute force method and improve it.

    1. Brute force O(2^n), this is the most straight forward solution, just try all the moves.
        int jump(vector<int>& nums) {
            return jump(0,nums);    
        }
        int jump(int p, vector<int>& nums) {
            int n = nums.size();
            if(p == n-1) return 0; //end is reached
            int range = p+nums[p];
            if(range >= n-1) return 1; //end can be reached by 1 jump from p
            int ret = n, mj; // n is larger than max jumps (n-1)
            for(int i=range;i>p;i--) {
                if ((mj = jump(i,nums)) == 1) return 2; //end can be reached by 2 jumps from p
                ret = min(ret,mj);
            }
            return ret+1;
        }
    

    Similar to editorial of jump game, we can immediately optimize it by memoization and dynamic programming to O(n^2).

        int jump(vector<int>& nums) {
            vector<int> mem(nums.size(),-1);
            return jump(0,nums,mem);    
        }
        int jump(int p, vector<int>& nums, vector<int>& mem) {
            int n = nums.size();
            if(p == n-1) return 0;
            int range = p+nums[p];
            if(range >= n-1) return 1;
            if(mem[p]>=0) return mem[p];
            int ret = n, mj;
            for(int i=range;i>p;i--) {
                if ((mj = jump(i,nums,mem)) == 1) return mem[p]=2;
                ret = min(ret,mj);
            }
            return mem[p] = ret+1;
        }
    
        int jump(vector<int>& nums) {
            int n = nums.size();
            vector<int> dp(n,n);
            dp[n-1]=0;
            for(int i=n-2;i>=0;i--) {
                int range = i+nums[i];
                if (range >= n-1) { 
                    dp[i]=1;
                    continue;
                }
                for(int j = range; j > i; j--) {
                    if(dp[j]==1) {
                        dp[i]=2;
                        break;
                    }
                    dp[i] = min(dp[i],dp[j]+1);
                }
            }
            return dp[0];    
        }
    
    1. Unfortunately, dp does not obviously lead to the optimal solution. Since the min jump path only visits some positions of the array, we do not need to try every position. We only need to try the postions on the min jump path. Starting from postion 0, the next position on the min jump path is the one that goes furthest from within the reach of current position. That's the greedy idea of the problem. Time complexity is O(n^2).
        int jump(vector<int>& nums) {
            return jump(0,nums);    
        }
        int jump(int p, vector<int>& nums) {
            int n = nums.size();
            if(p == n-1) return 0;
            int range = p+nums[p];
            if(range >= n-1) return 1;
            int nxt, max_reach = -1, reach;
            for(int i=range; i>p;i--) {
                if((reach=i+nums[i]) >= n-1) return 2;
                if(reach > max_reach) {
                    max_reach = reach;
                    nxt = i;
                }
            }
            return 1+jump(nxt,nums);
        }
    
    1. #2 is still O(n^2) because a position may be checked multiple times when selecting the next jump position. This is not necessary. If a position cannot reach further than the current min jump position, it is not a candidate for the next position. This improves the runtime to O(n).
        int jump(vector<int>& nums) {
            return jump(0,0,nums);    
        }
        int jump(int p, int range_start, vector<int>& nums) {
            int n = nums.size();
            if(p == n-1) return 0;
            int range = p+nums[p];
            if(range >= n-1) return 1;
            int nxt, max_reach = -1, reach;
            for(int i=range; i>range_start;i--) {
                if((reach=i+nums[i]) >= n-1) return 2;
                if(reach > max_reach) {
                    max_reach = reach;
                    nxt = i;
                }
            }
            return 1+jump(nxt,range, nums);
        }
    
    1. rewrite #3 iteratively and improve to constant space.
        int jump(vector<int>& nums) {
            int jumps=0, cur_pos = 0, n = nums.size(), pre_range = -1;
            while(cur_pos != n-1) {
                jumps++;
                int range = cur_pos+nums[cur_pos];
                if(range >= n-1) return jumps;
                int max_reach = -1, reach;
                for(int i=range; i > pre_range;i--) {
                    if((reach=i+nums[i]) >= n-1) return jumps+1;
                    if(reach > max_reach) {
                        max_reach = reach;
                        cur_pos = i;
                    }
                }
                pre_range = range;
            }
            return jumps;    
        }
    
    1. The problem only asks for the min number of jumps. So we do not have to figure out each jump position. We only need to store the max_reach of the previous jump position. If we go beyond that, we need one more jump.
        int jump(vector<int>& nums) {
            int pre=0, cur=0, jumps=0;
            for(int i=0;i<nums.size();i++) {
                if(i>pre) {
                    jumps++;
                    pre = cur;
                }
                cur = max(cur, i+nums[i]);
            } 
            return jumps;    
        }
    

  • 1
    W

    awesome, so many ways to solve this problem, although a little hard to understand each approach. -- Stephen Pokemon


Log in to reply
 

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