Posted on 2014-01-11 01:43
Uriel 閱讀(170)
評論(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 };