45. 跳跃游戏 II

主要练dp的定义

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        //状态定义
        //dp[i]:到达位置i的最少跳跃次数
        //初始化,初始化为无穷大
        Arrays.fill(dp, Integer.MAX_VALUE);
        //最开始就位于下标0,所以次数为0
        dp[0] = 0;
        //状态转移
        //从i向前搜索，如果遇到位置k，且满足 k + nums[k] >=i，
        //尝试更新dp[i]，即dp[i] = min(dp[i], dp[k]+1)
        for(int i = 1; i < n; i++){
            for(int k = 0; k < i; k++){
                if(k + nums[k] >= i){
                    dp[i] = Math.min(dp[i], dp[k] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}