貪心算法-帶貪心策略的證明過(guò)程
給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。
判斷你是否能夠到達(dá)最后一個(gè)位置史翘。
示例 1:
輸入:
[2,3,1,1,4]
輸出:true
解釋: 從位置 0 到 1 跳 1 步, 然后跳 3 步到達(dá)最后一個(gè)位置。
示例 2:輸入:
[3,2,1,0,4]
輸出: false
解釋: 無(wú)論怎樣，你總會(huì)到達(dá)索引為 3 的位置恶座。但該位置的最大跳躍長(zhǎng)度是 0 ， 所以你永遠(yuǎn)不可能到達(dá)最后一個(gè)位置沥阳。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/jump-game
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有跨琳。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處桐罕。
貪心策略
假設(shè)我們現(xiàn)在在索引 i 的位置脉让。
1、如果索引 i 的值為 功炮，那么我們不可能再繼續(xù)前進(jìn)了溅潜；如果此時(shí)索引
i 就是最后一個(gè)位置，返回 true薪伏，否則滚澜，返回 false。
2嫁怀、如果索引 i 的值不為 设捐，那么我們下一步可以走到索引
而在 我們又可以走到索引
我們選取索引 的原則是使得
取得最大值。（這一步是貪心策略的體現(xiàn)）
貪心策略的證明
1塘淑、如果此時(shí)i + k + p的最大值仍然小于n - 1萝招，說(shuō)明經(jīng)過(guò)此步還未能抵達(dá)數(shù)組中最后一個(gè)元素。
對(duì)于索引i而言存捺，假設(shè)索引i下一步的最優(yōu)解為索引i + k槐沼。索引i + k的下一步所能到達(dá)的范圍是[i + k + 1, i + k + nums[i + k]]。
假設(shè)索引i + k不是索引i下一步的最優(yōu)解捌治，索引i下一步的最優(yōu)解為索引i + j(j != k)岗钩。那么，索引i + j的下一步所能到達(dá)的范圍是索引[i + j + 1, i + j + nums[i + j]]肖油。
因?yàn)槲覀冞x取i + k的原則是使得i + k + p取得最大值凹嘲，顯然這里有i + j + nums[i + j] <= i + k + nums[i + k]。
a.如果j > k构韵，那么i + j + 1 > i + k + 1周蹭，索引i + j的下一步所能到達(dá)的范圍是小于索引i + k所能到達(dá)的范圍的。即如果索引i + j能到的地方疲恢，索引i + k也能到凶朗，但是索引i + k能到的地方，索引i + j卻不一定能到显拳。因此索引i下一步的最優(yōu)解一定只可能是i + k棚愤。
b.如果j < k，對(duì)于索引i + k + 1及其之后的索引位置，索引i + j的下一步所能到達(dá)的范圍是小于索引i + k所能到達(dá)的范圍的宛畦。即如果索引i + j能到的地方瘸洛，索引i + k也能到，但是索引i + k能到的地方次和，索引i + j卻不一定能到反肋。而對(duì)于索引i + k + 1之前的索引位置，索引i + k是到不了的踏施，索引i + j能到石蔗，但是此時(shí)其實(shí)多走了一步路。因?yàn)槲覀冏罱K肯定是要跨過(guò)索引i + k畅形，我們本可以一步到達(dá)索引i + k的位置养距，下一步就跨過(guò)索引i + k了，現(xiàn)在我們第一步到達(dá)索引i + j的位置日熬，下一步還不能保證跨過(guò)索引i + k棍厌。因此索引i下一步的最優(yōu)解一定只可能是i + k。
（2）如果此時(shí)i + k + p的最大值大于等于n - 1竖席，說(shuō)明經(jīng)過(guò)此步能抵達(dá)數(shù)組中最后一個(gè)元素定铜，顯然索引i + k是最優(yōu)解。
作者：617076674
鏈接：https://leetcode-cn.com/problems/two-sum/solution/tan-xin-suan-fa-dai-tan-xin-ce-lue-de-zheng-ming-g/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有怕敬。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)地啰，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處唱较。
