• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

LeetCode 45跳转游戏二区间数据处理


Recommended Posts

给定一个非负整数数字的数组,最初定位在数组的第一个索引处。

数组中的每个元素代表你在那个位置的最大跳跃长度。

您的目标是以最少的跳跃次数到达最后一个索引。

你可以假设你总能到达最后一个索引。

Solution

很容易想到\(dp\)表示以\(我\)结尾时的最小步数,考虑如何转移:

可以发现正向的\(dp\)比较容易:

\[dp[k]=\min(dp[k],dp[j] 1),\text{where } j nums[j]\geq k

\]

点击查看代码类别解决方案{

公共:

int jump(vectorint nums) {

int MAX=9999999

int DP[10005];

int n=nums。size();

for(int I=0;在;I)DP=MAX;

DP[0]=0;

如果(n==1)返回0;

否则{

for(int I=0;在;i ){

for(int ach=I 1;ach=I numsachn;ach ){

dp[ach]=min(dp[ach],1 DP);

}

}

返回DP[n-1];

}

}

};

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now