Jump Game, Jump Game II, Climbing Stairs

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

Solution

Simple 1D DP, update maxjump on each step, when we are at a place even maxjump cannot reach, return false.

public boolean canJump(int[] nums) {
    if(nums==null || nums.length==0 || nums.length==1) return true;
    int maxjump = 0;
    for(int i=0;i<nums.length;i++){
        if(i > maxjump) return false; // max jump streak cannot reach i
        if(nums[i]+i > maxjump){
            maxjump = nums[i]+i;
        }
        if(maxjump >= nums.length-1) return true;
    }
    return false;
}

---

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Solution

Similar to one, we record a lastjump var. Whenver we have to take a step(i>lastjump), update lastjump to maxjump(which is update on each index), as a simple greedy process.

public int jump(int[] nums) {
        int maxjump=0, lastjump=0, step=0;
        for(int i=0;i<nums.length;i++){
            if(i>lastjump){
                step++;
                lastjump=maxjump;
            }
            if(nums[i]+i>maxjump){
                maxjump=nums[i]+i;
            }
        }
        if(maxjump>=nums.length-1) return step;
        else return -1;
    }

---

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1D DP Solution

public static int climbStairs(int n) {
    if(n==1) return 1;
    int[] dp=new int[n];
    dp[0]=1;
    dp[1]=2;
    for(int i=2;i<n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n-1];
}

Recursive Solution

public static int climbStairs(int n) {
    int[] ways={0};
    climb(ways, 0, n);
    return ways[0];   
}
private static 
void climb(int[] ways, int len, int n){
    if(len>n) return;
    if(len==n){ways[0]++;return;}
    climb(ways, len+1, n);
    climb(ways, len+2, n);
}