首页 > 代码库 > leetcode. Jump Game
leetcode. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
本题可以使用数学归纳法(动态规划)解决：
能调到最后一个元素，用数学的语言来描述就是，必须存在i属于[0, n - 2], a[i] + i >= n - 1.
假设我们已经知道了n-1时的结果，能否推出n时的结果呢？我们记n = k时结果为ret[k].
1)如果ret[k-1] = false, 那么显然ret[k]=false.
2)若ret[k-1] = true, 必须存在i属于[0, k - 1], a[i] + i >= k， 那么ret[k] = true, 否则，ret[k] = false;
1 bool canJump(int A[], int n) 2 { 3 int *ret = new int[n], result; 4 ret[0] = true; 5 for (int i = 1; i < n; i++) 6 { 7 int max_pos = 0; 8 if (ret[i - 1] == false) 9 return false;10 11 for (int j = 0; j < i; j++)12 {13 max_pos = (A[j] + j) > max_pos ? (A[j] + j) : max_pos;14 }15 16 if (max_pos >= i)17 ret[i] = true;18 else19 ret[i] = false;20 }21 result = ret[n - 1];22 delete[] ret;23 return result;24 }
此时运行出现Time Limit Exceed, 运行超时。
仔细分析，11-14行的for循环是不需要的，可以申请max_pos[n]数组，保存每次得到的最大max_pos即可。
1 bool canJump(int A[], int n) 2 { 3 int *ret = new int[n], result; 4 int *max_pos = new int[n]; 5 ret[0] = true; 6 max_pos[0] = A[0] + 0; 7 for (int i = 1; i < n; i++) 8 { 9 if (ret[i - 1] == false)10 return false;11 12 max_pos[i] = max(max_pos[i - 1], (A[i] + i));13 if (max_pos[i - 1] >= i)14 ret[i] = true;15 else16 ret[i] = false;17 }18 19 result = ret[n - 1];20 delete[] ret;21 delete[] max_pos;22 23 return result;24 }
leetcode. Jump Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。