Jump Game 是一道简单的动归题目,通过判断A[j]+j 是否大于等于i 其中(i>j),来判断A[i]是否可达。题目需要注意的点是当仅有一个数的特殊情况
class Solution { public: bool canJump(int A[], int n) { if(A[0]==0&&n!=1)return false; for(int i=1;i<n;i++){ A[i]=max(A[i]+i,A[i-1]); if(A[i]<=i)return false; else if(A[i]>=n-1)return true; } return true; } };
Jump Game II 是上一题的进阶,需要找到到达末尾的最小的跳数,我开始仿照上面不断往后叠加,每次从j=0到A[j]叠加去求A[i],总是超时,后来将循环开始条件改为从A[j-1]-1,不过,这样改的结果是第一个元素的处理需要单独处理。
class Solution { public: int jump(int A[], int n) { if(A[0]==0&&n!=1)return n+1; int num[n]; memset(num,0,sizeof(num)); bool flag=0; for(int i=1;i<=A[0]&&i<n;i++)num[i]=1; for(int i=1;i<n;i++){ if(flag)break; for(int j=A[i-1]-1;j<=A[i];j++) if(i+j<n){ if(num[i+j]==0||num[i+j]>num[i]+1) num[i+j]=num[i]+1; } else {flag=1;break;} } return num[n-1]; /*for(int i=1;i<n;i++){ A[i]=max(A[i]+i,A[i-1]); if(A[i]<=i)return false; else if(A[i]>=n-1)return true; }*/ } };