Recursion & DP

跳跃游戏

time = N, space = 1

public int jump(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    
    // 跳了多少步
    int jump = 0;
    // 跳jump次到达的最远位置
    int cur = 0;
    // 跳jump + 1次到达的最远位置
    int next = 0;
    
    for (int i = 0; i < arr.length; i++) {
        if (cur < i) {
            jump++;
            cur = next;
        }
        next = Math.max(cur, i + arr[i]);
    }
    return jump;
}