領扣LintCode演算法問題答案-117. 跳躍游戲 II
目錄
- 117. 跳躍游戲 II
- 描述
- 樣例 1：
- 題解
- 鳴謝
117. 跳躍游戲 II
描述
給出一個非負整數陣列，你最初定位在陣列的第一個位置，
陣列中的每個元素代表你在那個位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
樣例 1：
輸入 : [2,3,1,1,4]
輸出 : 2
解釋 : 到達最后位置的最小跳躍次數是2(從下標0到1跳躍1個距離長度，然后跳躍3個距離長度到最后位置)
題解
public class Solution {
/**
* @param A: A list of integers
* @return: An integer
*/
public int jump(int[] A) {
// write your code here
int[] dp = new int[A.length];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 0; i < A.length; i++) {
if (dp[i] >= 0) {
for (int j = 1; j <= A[i] && i + j < A.length; j++) {
if (dp[i + j] < 0) {
dp[i + j] = dp[i] + 1;
} else {
dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
}
}
}
}
return dp[A.length - 1];
}
}
原題鏈接點這里
鳴謝
非常感謝你愿意花時間閱讀本文章，本人水平有限，如果有什么說的不對的地方，請指正，
歡迎各位留言討論，希望小伙伴們都能每天進步一點點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/178701.html
標籤：其他