跳躍游戲 II

貪心+雙指針+DP

• 簡(jiǎn)單來(lái)說(shuō)，對(duì)于下一個(gè)點(diǎn)j的最小次數(shù)，其必定是由離他最遠(yuǎn)的點(diǎn)跳過(guò)去的次數(shù)最少。

• 但是反過(guò)來(lái)不太行，如果是考慮當(dāng)前點(diǎn)，只讓他跳到最遠(yuǎn)的點(diǎn)的話(huà)，相當(dāng)于這個(gè)點(diǎn)對(duì)應(yīng)的下一步只有一個(gè)點(diǎn)，但這是不對(duì)的。因?yàn)樗赡軐?duì)應(yīng)著多個(gè)點(diǎn)。但對(duì)于下一個(gè)點(diǎn)來(lái)說(shuō)，他的最優(yōu)只會(huì)有一個(gè)。

• 狀態(tài)定義 f[i] 為達(dá)到第i個(gè)位置所需要的最少步數(shù) 轉(zhuǎn)移方程： f[i] = f[j]+1；

public int jump(int[] nums) { int n = nums.length; ? ?int[] f = new int[n]; ? ?for(int i=1,j=0;i<n;i++) { ? ? while(j+nums[j]<i) j++ ; // 只要j指針+當(dāng)前對(duì)應(yīng)的可跳步數(shù)是能夠到達(dá)i的，就不用更新j指針。 ? ? ? ?f[i] = f[j] + 1; ? ?} ? ?return f[n-1] ; }

純貪心

• 按照正常的想法，對(duì)于每一步，可以選擇他跳最遠(yuǎn)的地方，但是要看這一步的跳躍+下一步的跳躍距離來(lái)決定哪個(gè)是該選的，能跳最遠(yuǎn)的。且，指針不能直接跳過(guò)去，對(duì)于每一個(gè)元素，都需要進(jìn)行一次遍歷。因?yàn)闆Q定的只有到第二層，而實(shí)際情況到了第n層。

• 在具體的實(shí)現(xiàn)中，我們維護(hù)當(dāng)前能夠到達(dá)的最大下標(biāo)位置，記為邊界。我們從左到右遍歷數(shù)組，到達(dá)邊界時(shí)，更新邊界并將跳躍次數(shù)增加1.

• 在遍歷數(shù)組時(shí)，我們不訪(fǎng)問(wèn)最后一個(gè)元素，這是因?yàn)樵谠L(fǎng)問(wèn)最后一個(gè)元素之前，我們的邊界一定大于等于最后一個(gè)位置，否則就無(wú)法跳到最后一個(gè)位置了。如果訪(fǎng)問(wèn)最后一個(gè)元素，在邊界正好為最后一個(gè)位置的情況下，我們會(huì)增加一次【不必要的跳躍次數(shù)】，因此我們不必訪(fǎng)問(wèn)最后一個(gè)元素。

public int jump(int[] nums) { int length = nums.length; ? ?int end = 0; ? ?int maxPosition = 0; ? ?int steps = 0; ? ?for(int i=0;i<length-1;i++){ ? ? maxPosition = Math.max(maxPosition,i+nums[i]); ? ? ? ?if(i==end) { ? ? ? ? end = maxPosition; ? ? ? ? ? ?steps++; ? ? ? ?} ? ?} ? ?return steps ; }