思路
利用动态规划来获取最大跳跃次数
解题方法
解决动态规划必须要定义状态含义、状态转移方程、入口状态和边界条件。
- 状态含义：dp(i)表示到下标为i的元素最大跳跃数；
- 状态转移方程：dp(i)=max{dp(i),dp(j)+1}，其中满足-target<=nums[i]-nums[j]<=target。
- 入口状态：当在下标为0的元素时最大跳跃式为0，表示为dp[0]=0。
- 边界条件：即在最后一个元素length-1时，为需要获取的最大跳跃数。
复杂度
- 时间复杂度: 需要进过两次循环，所以时间复杂度为： O ( n 2 ) O(n^2)O(n2)
- 空间复杂度: 只需要大小为n的数组，所以空间复杂度为： O ( n ) O(n)O(n)
Code
class Solution { public int maximumJumps(int[] nums, int target) { int len = nums.length; int dp[] = new int[len]; Arrays.fill(dp, -1); dp[0] = 0; for (int i = 1; i < len; i++) { for (int j = 0; j < i; j++) { if (Math.abs(nums[i] - nums[j]) <= target && dp[j] != -1) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } return dp[len - 1]; } }
