jump game
Jump Game
- $1.题目描述
- $2.思路分析（存在型动态规划）
- 1.确定状态
- 2.转移方程
- 3.初始条件和边界情况
- 4.计算顺序
- $3.代码展示
$1.题目描述
$2.思路分析（存在型动态规划）
1.确定状态
- 最后一步：如果青蛙能跳到最后一块石头n-1,我们考虑他跳的最后一步，这一步是从石头i跳过来，i
- 这需要两个条件同时满足：
- 1.青蛙可以调到石头i;
- 2.最后一步不超过跳跃的最大距离：n-1-i <= ai
- 子问题
那么，我们需要知道青蛙能否跳到石头i（i从而确定状态：设f[i]表示青蛙能不能跳到石头j
2.转移方程
OR0<=i
f[i] (能跳到石头i) 并且 i>a[i]>=j 能跳到j
3.初始条件和边界情况
初始条件：f[0]=True,因为青蛙一开始就在石头0
边界情况：因为枚举的i的情况并不会越界，所以此题不用考虑边界情况
4.计算顺序
1.设f[j]表示青蛙能不能跳到石头j
2.f[j]=OR0<=i= j)
3.初始化f[0]=True
4.计算f[1],f[2],…,f[n-1]
5.答案为f[n-1]
时间复杂度O(N^2^),空间复杂度（数组大小）：O（n） j=1 ----> i=0 j=2 ----> i=0,1 j=3 ----> i=0,1,2 j=4 ----> i=0,1,2,3 j=5 ----> i=0,1,2,3,4 时间复杂度 1+2+3+...+n-1 = n*(n-1)/2
$3.代码展示
public class Solution { public boolean canJump(int[] A) { int n = A.length; boolean[] f = new boolean[n]; f[0]=true;//initialization for(int j=1;j<n;j++) { f[j]=false; //之前的石头i //最后一步是从i到j for(int i=0;i<j;i++) { if(f[i] && i+A[i]>=j){ //A[i]是石头上标的数值，青蛙能跳的距离x <= A[i],不一定要跳A[i]这么远 f[j]=true; break; } } } return f[n-1]; } }
本题还有种方法为贪心算法时间复杂度为O(N)
思路：从数组的第一个位置开始，往后一个一个遍历数组，当所遍历的位置没有超出reach范围时，可根据跳力（即每块石头上的数字）更新可reach的范围，可遍历的范围必须小于等于reach值。若可reach范围可覆盖数组最后一个位置，则可到达；若不可覆盖，则不可到达。
class Solution1{ public boolean jumpGame(int[] num){ int N=num.length,reach=0; for(int i=0;i<=reach;i++){ if(reach<i+num[i]) reach=i+num[i]; if(reach>=N-1) return true; } return false; } }
Summary:
