题目:输入数组,数组元素表示该处可跳跃的最大长度,求是否可以从第一个元素到达最后一个元素,若可到达最求出最少的跳跃次数
分析:判断是否可跳到最后,dp[i]=max(dp[i-1],i+arr[i]) (i<dp[i-1])注:dp[i]表示第一个元素通过前i个元素跳跃的最大长度
判断最少跳跃次数,dp[i]=min(dp[j]+1,dp[i]) (i<j<=i+arr[i]) 注:dp[i]表示第i个元素到最后元素跳跃的最少次数
说明:从第一个元素[0]跳跃到最后一个元素[n-1],跳跃长度>=n-1,而非n
/*跳跃游戏-是否可跳跃到最后一个元素*/ #include <iostream> using namespace std; int arr[502],n; int canjump() { int global=0,local=0; for(int i=0;i<n;i++) { if(global<i) return 0; global=max(global,i+arr[i]); } if(global>=n-1) return 1; else return 0; } int main() { while(cin>>n) { for(int i=0;i<n;i++) cin>>arr[i]; if(canjump()==1) cout<<"true"; else cout<<"false"; } } /*跳跃游戏二-求跳跃到最末元素最少的次数*/ #include <iostream> using namespace std; int n,arr[502],dp[502]; int main() { cin>>n; for(int i=0;i<n;i++) { cin>>arr[i]; dp[i]=0xFFFF; } dp[n-1]=0; for(int i=n-2;i>=0;i--) { int k=i+arr[i]; for(int j=i+1;j<=k&&j<n;j++) { dp[i]=min(dp[i],dp[j]+1); } } cout<<dp[0]<<endl; }