注意，貪心法是錯(cuò)誤的！貪心法在lintCode能夠AC,leetCode不能AC。因?yàn)檫@道題是一道最優(yōu)題，而貪心法不能保證最優(yōu)
題意：
給出一個(gè)非負(fù)整數(shù)數(shù)組，你最初定位在數(shù)組的第一個(gè)位置。
數(shù)組中的每個(gè)元素代表你在那個(gè)位置可以跳躍的最大長(zhǎng)度?！ ?
判斷你是否能到達(dá)數(shù)組的最后一個(gè)位置。
樣例：
A = [2,3,1,1,4]，返回 true.
A = [3,2,1,0,4]，返回 false.
注意事項(xiàng)：
這個(gè)問題有兩個(gè)方法，一個(gè)是貪心和 動(dòng)態(tài)規(guī)劃。
貪心方法時(shí)間復(fù)雜度為O（N）。
動(dòng)態(tài)規(guī)劃方法的時(shí)間復(fù)雜度為為O（n^2）。
我們手動(dòng)設(shè)置小型數(shù)據(jù)集，使大家可以通過測(cè)試的兩種方式。這僅僅是為了讓大家學(xué)會(huì)如何使用動(dòng)態(tài)規(guī)劃的方式解決此問題。如果您用動(dòng)態(tài)規(guī)劃的方式完成它，你可以嘗試貪心法，以使其再次通過一次
1.貪心法
??正如注意事項(xiàng)所說的，這道題有種解法。我們先來看看貪心法。
(1).解題思路
??貪心法的思路非常的簡(jiǎn)單，那就是，當(dāng)跳到一個(gè)位置上，我們?cè)诋?dāng)前位置到當(dāng)前位置能達(dá)到的最大位置范圍找到最大值，如果最大值的index + 最大值大于當(dāng)前位置能達(dá)到的最大位置的index，那么選擇跳到最大值的index去，反之則跳到當(dāng)前位置能達(dá)到的最大位置。
(2).代碼
public boolean canJump(int[] A) {
//當(dāng)前跳的位置
int index = 0;
while (index < A.length - 1) {
if (A[index] == 0) { // 如果當(dāng)前的值為0，就跳不動(dòng)了，那么肯定為false
return false;
}
//最大值
int max = Integer.MIN_VALUE;
//最大值的index
int maxIndex = 0;
for (int i = index + 1; i < A.length && i < index + A[index]; i++) {
if (max < A[i]) {
max = A[i];
maxIndex = i;
}
}
//如果最大值和最大值的index的和大于當(dāng)前index + A[index]
//表示下次調(diào)到最大值的位置上去
if (maxIndex + max > index + A[index]) {
index = maxIndex;
} else {
//反之則跳到index + A[index]
index = index + A[index];
}
}
return true;
}
2.動(dòng)態(tài)規(guī)劃
(1).解題思路
??說實(shí)話，自己的動(dòng)態(tài)規(guī)劃還是很弱，有待加強(qiáng)！
??動(dòng)態(tài)規(guī)劃的思路相對(duì)來說要復(fù)雜一下，我們這里分兩種情況來討論
??第一步,定義一個(gè)dp一維數(shù)組，用來記錄每個(gè)位置是否能夠達(dá)到終點(diǎn)。比如，dp[i],表示在i位置，是否能夠跳到終點(diǎn)，如果能，為true；反之為false。
??第二步，dp[i]是否能夠跳到終點(diǎn)，這里主要分為兩種情況：
??1.如果當(dāng)前位置可以直接跳到終點(diǎn)，也就是說i + A[i] >= A.length() - 1,那么直接讓dp[i] 為true就行了。
??2.如果當(dāng)前位置不能直接跳到終點(diǎn)，但是可以借助其他位置跳到終點(diǎn)，那么dp[i]也為true。這里設(shè)置為true有兩個(gè)條件，假設(shè)它借助j位置，首先dp[j]必須true，其次它必須能夠跳到j(luò)位置，也就是說i + dp[i] >= j。
??經(jīng)過簡(jiǎn)單的分析，應(yīng)該能夠理解到這個(gè)解法的思路吧?。?！
(2).代碼
public boolean canJump(int[] A) {
//dp數(shù)組表示當(dāng)前的位置是否能夠跳到最后
boolean dp[] = new boolean[A.length];
//默認(rèn)最后一個(gè)為true
dp[A.length - 1] = true;
for (int i = A.length - 2; i >= 0; i--) {
//如果當(dāng)前位置能夠直接跳到終點(diǎn)，直接設(shè)置為true
if (i + A[i] >= A.length - 1) {
dp[i] = true;
}
for (int j = i; j < A.length - 1; j++) {
//設(shè)置為true的條件是：
//1.借助的j點(diǎn)必須為true
//2.必須能夠跳到j(luò)點(diǎn)來(i + A[i] >= j)
if (dp[j] && i + A[i] >= j) {
dp[i] = true;
}
}
}
return dp[0];
}
