首页 > 代码库 > Jump Game II

Jump Game II

My naive $O(n^2)$ running time solution:

class Solution {public:    int jump(int A[], int n) {        if(1 == n) return 0;        int maxL = (1<<31) - 1;        int *jumps = new int[n];        jumps[0] = 0;                for(int i = 1; i < 1; ++i)            jumps[i] = maxL;                    for(int i = 1; i < n; ++i)            for(int j = 0; j < i; ++j)  //offer information for i                if(A[j] >= (i-j) && jumps[j]+1 < jumps[i])                    jumps[i] = jumps[j] + 1;                int result = jumps[n-1];        delete []jumps;                if(result != maxL)            return result;                    return -1;    }};

 

What we need to do is just optimizing the code. In fact, we only need to optimize one place:

for(int j = 0; j < i; ++j)  //offer information for i    if(A[j] >= (i-j) && jumps[j]+1 < jumps[i])        jumps[i] = jumps[j] + 1;

 

Here, we use $jumps[pos]$ to store the minimum jumps to reach position $pos$.

In fact, once we get the if statement, we can break. Because the remaining results must be greater than or equal to the current results of $jumps[j] + 1$.

Let‘s give a proof.

Let‘s suppose existing $s$, where $j < s < i$, such that $jumps[s] + 1 < jumps[j] + 1$, i.e. $jumps[s] < jumps[j]$. Without losing the generality, we can assume $s$ is the first element satisfy these conditions, which means the element $s‘$, where $j < s‘ < s$, satisfying $jums[s‘] \geq jumps[j]$.

  • We can use induction. Assume

 

  • Let‘s consider the last position, $k$, to jump to $s$, which means $jumps[k] + 1 = jumps[s]$.
    1. If $k < j$: because the array can jump to $s$ from $k$, and $k < j < s$, it also means we can jump to $j$ from $k$.
      So $jumps[j] \leq jumps[k]+1=jumps[s]$
    2. If $k = j$: that means $jumps[j] + 1 = jumps[s]$, i.e. $jumps[j] < jumps[s]$.
    3. If $k > j$: because $s$ is the first element satisfy $jumps[s] < jumps[j]$. So $jumps[j] \leq jumps[k] < jumps[s]$.

 

All these situations are contradictions. So, we finish our proof.

 

Thus we can optimize our code like: 

for(int j = 0; j < i; ++j)  //offer information for i    if(A[j] >= (i-j) && jumps[j]+1 < jumps[i]){        jumps[i] = jumps[j] + 1;        break;    }

 

One more slight tricky ignoring Time Limit Exceed, we can put the initialization into our second for loop. The final code is:

class Solution {public:    int jump(int A[], int n) {        if(1 == n) return 0;        int maxL = (1<<31) - 1;        int *jumps = new int[n];        jumps[0] = 0;                for(int i = 1; i < n; ++i){            jumps[i] = maxL;            for(int j = 0; j < i; ++j)  //offer information for i                if(A[j] >= (i-j) && jumps[j]+1 < jumps[i]){                    jumps[i] = jumps[j] + 1;                    break;                }        }                int result = jumps[n-1];        delete []jumps;                if(result != maxL)            return result;                    return -1;    }};

 

Jump Game II