領釦LintCode演演算法問題答案-117. 跳躍遊戲 II

117. 跳躍遊戲 II

描述

給出一個非負整數陣列，你最初定位在陣列的第一個位置。

陣列中的每個元素代表你在那個位置可以跳躍的最大長度。

你的目標是使用最少的跳躍次數到達陣列的最後一個位置。

樣例 1：

輸入 : [2,3,1,1,4]
輸出 : 2
解釋 : 到達最後位置的最小跳躍次數是2(從下標0到1跳躍1個距離長度，然後跳躍3個距離長度到最後位置)

題解

public class Solution {
    /**
     * @param A: A list of integers
     * @return: An integer
     */
    public int jump(int[] A) {
        // write your code here
        int[] dp = new int[A.length];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 0; i < A.length; i++) {
            if (dp[i] >= 0) {
                for (int j = 1; j <= A[i] && i + j < A.length; j++) {
                    if (dp[i + j] < 0) {
                        dp[i + j] = dp[i] + 1;
                    } else {
                        dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                    }
                }
            }
        }

        return dp[A.length - 1];
    }
}

原題連結點這裡

鳴謝

非常感謝你願意花時間閱讀本文章，本人水平有限，如果有什麼說的不對的地方，請指正。
歡迎各位留言討論，希望小夥伴們都能每天進步一點點。