前言
貪心算法是指在對(duì)問題求解時(shí)，不從整體最優(yōu)考慮，只是局部的最優(yōu)考慮。所以貪心算法可能不能達(dá)到最優(yōu)解，貪心算法也有正確的時(shí)候，求最小生成樹的Prim算法和Kruskal算法都是漂亮的貪心算法。貪心算法的基本思路是從問題的某一個(gè)初始解出發(fā)一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測(cè)度，每一步都要確保能獲得局部最優(yōu)解。
問題描述
給定一個(gè)非負(fù)整數(shù)數(shù)組nums，你最初位于數(shù)組的第一個(gè)下標(biāo)。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。
判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)。
示例1： 示例2：
輸入:nums = [2,3,1,1,4] 輸入：nunms = [3,2,1,0,4]
輸出：true 輸出：false
解決方案
一般碰到能否走完，走的更遠(yuǎn)等題目，優(yōu)先考慮貪心和動(dòng)態(tài)規(guī)劃兩種方式，此題在這里講的貪心，貪心算法更適合這一道題。示例1：此題的意思是當(dāng)從數(shù)組下標(biāo)為0的位置開始，下標(biāo)為0的位置上的元素為2就可以跳一次或兩次，如果跳一次就會(huì)跳到下標(biāo)為1的位置，1位置的元素為3，那么現(xiàn)在可以跳躍1次2次3次，不管跳幾次最終都能達(dá)到終點(diǎn)；如果跳兩次，也可以到達(dá)終點(diǎn)。示例2：當(dāng)從下標(biāo)為0的位置開始跳，可以跳1次或2次或3次，但不管跳幾次都會(huì)跳到元素0的位置，然后就跳不動(dòng)了，就不能跳到終點(diǎn)。通過分析發(fā)現(xiàn)凡是數(shù)組中不含0的數(shù)組都可以跳到最后一個(gè)元素，如果數(shù)組中含0，那么就不能跳到最后一個(gè)元素。從下圖可以清楚的看到過程。
紅色代表起始跳2次，藍(lán)色代表起始跳1次，跳的次數(shù)小于等于該位置的元素大小。
結(jié)語
此題運(yùn)用貪心法就比較容易理解，就容易理解題目意思?？赡苓€有更簡(jiǎn)單的算法，后期我會(huì)進(jìn)一步研究。
實(shí)習(xí)編輯：衡輝
稿件來源：深度學(xué)習(xí)與文旅應(yīng)用實(shí)驗(yàn)室（DLETA）
聯(lián)系客服
