55. Jump Game

Problem

This problem says that given an array of numbers, each number represents the farthest he can jump from his current position, and find out if he can (and has the ability to) move to the last index.

Algorithm

I used capable in the problem description, i.e. it doesn't have to end up at the last index, it just needs to be able to jump to a position greater than or equal to that index.

Another thing to note about this topic is that nums[i] can be 0, i.e. I can't jump one step at the current position.

I should look at the examples and restrictions more carefully on each topic, and consider boundary cases carefully.

Back to the topic algorithm, for this topic we can traverse each position from the beginning, find the farthest it can jump to at that position, and return true if it reaches the end, otherwise continue down the line according to the farthest distance he can go (maxReach). If it doesn't reach the end or the position it can jump to doesn't reach the end and beyond, then it returns false.

Code

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0 + nums[0];
        for (int i = 0; i < nums.length && i <= maxReach; i++) {
            if (maxReach >= nums.length - 1) {
                return true;
            }
            maxReach = Math.max(i + nums[i], maxReach);
        }
        return false;
    }
}

More - Basic steps of greedy algorithm (idea)

1. Build a mathematical model of the topic and convert it to a extreme value problem. See how the whole problem derives the final result.
2. Solve the problem for each subproblem.
3. Apply the local optimal solution in another iteration to derive the global optimal solution.

Taking this topic as an example, in the first step we describe the problem as finding the farthest distance for each step and keep going until we get to the farthest position he can go; in the second step find the farthest distance for each iteration or each step; in the third step apply the farthest distance obtained in each iteration to the farthest distance we can go and keep iterating until we get to the farthest place we can go.