55. Jump Game

Let dp[i] be the maximum steps left on position i. So the dp state transition function is:

dp[i] = max(dp[i-1], nums[i-1])-1 (-1 means one step from previous position to current position)

Once dp[i] drops below 0, we are sure that we can't move forward and thus we can't reach the end.

1:  class Solution {  
2:  public:  
3:    bool canJump(vector<int>& nums) {  
4:      vector<int> dp(nums.size(), 0);  
5:      for (int i = 1; i < nums.size(); i++) {  
6:        dp[i] = max(dp[i-1], nums[i-1])-1;  
7:        if (dp[i] < 0) return false;  
8:      }  
9:      return true;  
10:    }  
11:  };  

This can be improved to be O(1) space as we only care about the previous state.

1:  class Solution {  
2:  public:  
3:    bool canJump(vector<int> &nums) {  
4:      int steps = 0;  
5:      for (int i = 1; i < nums.size(); i++) {  
6:        steps = max(steps, nums[i-1])-1;  
7:        if (steps < 0) return false;  
8:      }  
9:      return true;  
10:    }  
11:  };