C++ DP 13ms with detailed explanation.


  • 0
    E
    class Solution {
    public:
        int jump(vector<int>& A) {
            if (A.empty()) {
                return 0;
            }
            int n = A.size();
            // creat a vector to save the min steps to each position.
            vector<int> minsteps(n, INT_MAX);
            // start with the first position, so it needs 0 steps.
            minsteps[0] = 0;
            // start position for inner loop
            int start = 0;
            for (int i = 1; i < n; i++) {
                for (int j = start; j < i; j++) {
                    // find the the first position before i is able to jump to i
                    if (A[j] >= i - j) {
                        //save the position of j as the next start position
                            start = j;
                        //get the min steps of position i.
                            minsteps[i] = minsteps[j] + 1;
                        break;
                    }
                }
                 // check if the start position is able to jump to the end.
                if (A[start] >= n - start - 1) {
                    return minsteps[i];
                }
            }
            return minsteps[n - 1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.