題目要求

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。

你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。

示例:

輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。
說(shuō)明:

假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置。

解題思路

1.使用動(dòng)態(tài)規(guī)劃，dp[i]代表從下標(biāo)為0的位置走到第i步需要的最少跳躍次數(shù).時(shí)間復(fù)雜度是0(N^2)

 public int jump(int[] a) {
     int[] dp = new int[a.length];
        dp[0] = 0;
        for (int i = 1; i < a.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (i - j <= a[j]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[a.length - 1];
    }

2.遍歷一次數(shù)組，每走一步的時(shí)候判斷當(dāng)前數(shù)字范圍內(nèi)能夠走到的最遠(yuǎn)距離。時(shí)間復(fù)雜度O(n).

微信圖片_20190419223139.jpg

   public int jump(int[] a) {

        int jumpTimes = 0;
        int maxPosition = 0;
        int reached = 0;
        for (int i = 0; i < a.length; i++) {
            if (reached < i) {
                jumpTimes++;
                reached = maxPosition;
            }
            maxPosition = Math.max(maxPosition, i + a[i]);
        }
        return jumpTimes;
    }