Posted on 2014-01-11 01:43
Uriel 阅读(159)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
这题昨天携程网络赛有原题，于是今天来做了一下，不过自己还是太挫，只想到裸O(n^2)的dp，据说会超时，但是又想不出优化，于是瞟了一眼解题报告，瞬间恍然大悟...
第二重循环不需要从头开始再扫一遍，只需要从目前能到达的最远点开始即可!
两题方法完全一样~
Jump Game
1 class Solution {
2 public:
3 bool canJump(int A[], int n) {
4 int dp[1000010], mx = 0;
5 memset(dp, 0, sizeof(dp));
6 for(int i = 0; i < n; ++i) {
7 for(int j = mx - i + 1; j <= A[i] && i + j < n; ++j) {
8 if(!i || dp[i])
9 dp[i + j] = dp[i] + 1;
10 }
11 mx = max(mx, A[i] + i);
12 }
13 if(dp[n - 1] || n == 1) return true;
14 return false;
15 }
16 };
Jump Game II
1 class Solution {
2 public:
3 int jump(int A[], int n) {
4 int dp[1000010], mx = 0;
5 memset(dp, 0, sizeof(dp));
6 for(int i = 0; i < n; ++i) {
7 for(int j = mx - i + 1; j <= A[i] && i + j < n; ++j) {
8 dp[i + j] = dp[i] + 1;
9 }
10 mx = max(mx, A[i] + i);
11 }
12 return dp[n - 1];
13 }
14 };