leetcode55. 跳跃游戏 45. 跳跃游戏 II

55. 跳跃游戏

 

 

45. 跳跃游戏 II

 

我写的第一份通过的代码，问题在于重复更新浪费不少时间，内层循环可能会重复更新许多已经确定不是最优解的位置。

class Solution {public int jump(int[] nums) {int n = nums.length;int[] dp = new int[n]; //dp[i]表示到达此处的最小跳跃次数for(int i = 1;i < n;++i)  dp[i] = 100001;for(int i = 0;i < n;++i){for(int j = i + 1;j <= i + nums[i] && j < n;++j){dp[j] = Math.min(dp[j],dp[i] + 1);}}return dp[n-1];}
}