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 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 - 1
return 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];
}
}