1.題目
給你一個非負整數陣列 nums ，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
你的目標是使用最少的跳躍次數到達陣列的最后一個位置，
假設你總是可以到達陣列的最后一個位置，
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2， 從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000
2.題目分析
這是一道動態規劃的題目，思路求解和跳躍游戲1類似，只不過現在題目假設從起點都能到終點，找從起點到終點的最小跳數，
? 設dp[i]表示到達下標i的跳數，dp[0]=0
? 當j+nums[j]<length-1;dp[i]=dp[j]+1(i在[j,j+nums[j]]之間&&dp[j]==0 || dp[i]>(j+nums[j]))
? 當j+nums[j]>=length-1;return dp[j]+1
3.代碼
class Solution {
public int jump(int[] nums) {
int length=nums.length;
int dp[]=new int[length];
int flag=0;
if(length == 1)
return 0;
for(int i=0;i<length;i++)
{
int temp=i+nums[i];
int sum=dp[i]+1;
//System.out.println("flag"+flag+" temp"+temp);
if(temp>flag && temp<(length-1))
{
for(int j=flag+1;j<=temp;j++)
{
if(dp[j] == 0 ||(dp[j]!=0 && dp[j]>sum))
dp[j]=sum;
//System.out.println("dp[j]:"+dp[j]);
}
flag=temp;
}
else if(temp>=(length-1))
{
//System.out.println("sum1:"+sum);
return sum;
}
}
return dp[length-1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/517612.html
標籤：其他