首页 > 代码库 > 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]$.
- 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]$- If $k = j$: that means $jumps[j] + 1 = jumps[s]$, i.e. $jumps[j] < jumps[s]$.
- 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