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;
}
};
原文：http://www.cnblogs.com/kid551/p/4114594.html