solved 'Jump Game II' on LeetCode http://oj.leetcode.com/problems/jump-game-ii/

jump_game_ii.cpp

/*
1. first using DP, O(n^2), TLE.
2. then try spliting arrays to intervals by 
    taking the maximum reach as the boundary.
*/
class Solution {
public:
    int jump(int A[], int n) {
        if (A[0] == 0 || n == 1) return 0;
        int iter = 1, intervalEnd = A[0], res = 1;
        while (n-1 > intervalEnd) {
            int maxOfInterval = 0;
            for (;iter <= intervalEnd;++iter) {
                if (A[iter]+iter > maxOfInterval) maxOfInterval = A[iter]+iter;    
            }
            intervalEnd = maxOfInterval;
            ++res;
        }
        return res;
    }
};