【动态规划】45. 跳跃游戏 II
45. 跳跃游戏 II
解题思路
-
int[] memo;：定义一个数组memo，用来作为备忘录，存储从每个索引位置跳到数组末尾所需的最小跳跃次数。
-
Arrays.fill(memo, n);：在开始计算之前，先将memo数组的所有元素初始化为n。这里的n是输入数组nums的长度，初始化为n是因为从任何位置到最后位置的跳跃次数不可能大于n-1。
-
dp(nums, 0);：调用dp函数，从索引0开始计算到达最后位置的最少跳跃次数。
-
dp函数：这个函数是解题的核心，它递归地计算从当前位置p到最后位置所需的最少跳跃次数。
-
如果p已经大于或等于n-1（即已经到达或超过了数组的最后位置），则不需要再跳跃，返回0。
-
如果memo[p]不等于n，说明这个位置的最少跳跃次数已经被计算过了，直接返回memo[p]的值。
-
对于当前位置p，尝试所有可能的跳跃步数（从1到nums[p]），并递归地调用dp函数计算每一种选择后的最少跳跃次数。选择所有可能中的最小值加1（当前这一跳）作为memo[p]的值。
class Solution {// List<Integer> memo = new ArrayList<>();// 作为备忘录记忆int[] memo;// 记录每一个索引位置跳跃最后一个位置要多少次public int jump(int[] nums) {// 动态规划int n = nums.length;// 初始化备忘录memo = new int[n];Arrays.fill(memo,n);// 所有元素全部初始化为n 因为从0 到n - 1 不会超过n - 1return dp(nums,0);}int dp(int[] nums,int p){// 返回值 从索引p跳到最后一个位置所需要的最少次数int n = nums.length;if(p >= n - 1){return 0;}// 判断子问题是不是计算过if(memo[p] != n){return memo[p];}int steps = nums[p];// 然后从当前位置可以选择跳跃 1 2 3 4 5 ... steps步for(int i = 1; i <= steps;i++){// 跳跃i步 到下一个位置 然后计算结果int subProbelm = dp(nums, p + i);// 取其中最小的作为最终结果memo[p] = Math.min(memo[p],subProbelm + 1);}return memo[p];}
}