描述
給出一個非負整數陣列，你最初定位在陣列的第一個位置，
陣列中的每個元素代表你在那個位置可以跳躍的最大長度，
判斷你是否能到達陣列的最后一個位置，
說明
陣列A的長度不超過5000，每個元素的大小不超過5000
樣例
- 樣例 1
輸入 : [2,3,1,1,4]
輸出 : true
- 樣例 2
輸入 : [3,2,1,0,4]
輸出 : false
挑戰
這個問題有兩個方法，一個是貪心和 動態規劃，
貪心方法時間復雜度為O（N），
動態規劃方法的時間復雜度為為O（n^2），
我們手動設定小型資料集，使大家可以通過測驗的兩種方式，這僅僅是為了讓大家學會如何使用動態規劃的方式解決此問題，如果您用動態規劃的方式完成它，你可以嘗試貪心法，以使其再次通過一次，
決議
const canJump = function (A) {
let k = 0;
for (let i = 0; i < A.length; i++) {
if (i > k) return false;
k = Math.max(k, i + A[i]);
}
return true;
}
運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/22408.html
標籤：其他