Leetcode 45. 跳躍游戲 II

動(dòng)態(tài)規(guī)劃

使用dp [ ] 記錄每個(gè)位置可達(dá)的最小步數(shù)，每到達(dá)一個(gè)點(diǎn)時(shí)，更新該點(diǎn)所能跳躍區(qū)間內(nèi)的所有點(diǎn)的dp值
時(shí)間復(fù)雜度較高

class Solution {public int jump(int[] nums) {int n = nums.length;int dp[] = new int [n];int N = 99999;Arrays.fill(dp, N);dp[0] = 0;for(int i = 0 ; i < n; i ++){for(int j = 1 ; j <= nums[i]; j ++){if(i + j < n)dp[i + j] = Math.min(dp[i + j], dp[i] + 1);}}return dp[n-1];}
}

優(yōu)化 雙指針

雙指針 l r 表示目前可達(dá)的區(qū)間左右端點(diǎn)，遍歷區(qū)間維護(hù)一個(gè)可達(dá)的最遠(yuǎn)距離maxPos
當(dāng) l r 相遇即區(qū)間遍歷結(jié)束后，將該區(qū)間內(nèi)可達(dá)的最遠(yuǎn)距離maxPos作為下一次跳躍的區(qū)間右端點(diǎn) r ，此時(shí)跳躍一步
當(dāng) r 可以到達(dá)邊界時(shí)，即結(jié)束遍歷
時(shí)間復(fù)雜度O(n)

class Solution {public int jump(int[] nums) {int n = nums.length;int l = 0;int r = 0;int maxPos = 0;int step = 0;while(r < n-1){maxPos = Math.max(maxPos, l + nums[l]);// 該區(qū)間已遍歷結(jié)束，更新區(qū)間右端點(diǎn)，此步跳出if(l == r){r = maxPos;step ++;}l ++;}return step;}
}