锐客网

  1. 首页 > it技术 > >

计蒜客|计蒜客 跳跃游戏二

今天继续写一道动态规划题目
给定一个非负整数数组，假定你的初始位置为数组第一个下标。
数组中的每个元素代表你在那个位置能够跳跃的最大长度。
你的目标是到达最后一个下标，并且使用最少的跳跃次数。
例如：
A=[2,3,1,1,4]，到达最后一个下标的最少跳跃次数为2。（先跳跃1步，从下标0到1，然后跳跃3步，到达最后一个下标。一共两次）
输入格式
第一行输入一个正整数n(1≤n≤100)，接下来的一行，输入n个整数，表示数组A。
输出格式
最后输出最少的跳跃次数。
样例输入
5
3 1 1 1 1
样例输出
2
解析 这道题目一开始我们应该会想到，我们要跳到最后一个位置，就把前面的每个位置遍历一遍，看看那个位置可以直接跳到最后一个位置，然后比较它们的大小，取最小的+1即可得到答案
可是，这样的话时间复杂度会很高，大概是n^2
但是我们用动态规划的思想自底向上的话就会轻松很多
例如题目给的2 3 1 1 4的例子
我们把2 3 1 1 4分别标记为1号位置到5号位置 即求从1号位置跳到5号位置的最少步数
从1号位置开始看，可以跳跃的最大步数是2，那么我们把2号位置和3号位置的最少步数置为1号位置的最少步数0加上1步（此时dp[2]=1 dp[3]=1），因为最多能跳到3号位置，而且之前2,3号位置没有其他方式可以到达，所以直接赋值。
然后开始遍历2号位，可以跳跃的最大步数是3，那么我们把3,4,5号位的最少步数置为dp[2]+1，由于dp[3]=1比dp[2]+1要小，所以dp[3]不改变，dp[4]和dp[5]赋值为dp[2]+1
【计蒜客|计蒜客 跳跃游戏二】以此类推所有位置只需要遍历一遍，时间复杂度大大降低，大概为n
代码

int dp[110]={0};
int main()
{
int n;
dp[1]=0;
int k=0;
int num=0;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&num);
for(k=1; k<=num&&i+k<=n; k++)
{
if(dp[i+k]==0||dp[i+k]>dp[i]+1)
{
dp[i+k]=dp[i]+1;
}
}
}
printf("%d\n",dp[n]);
return 0;
}

    推荐阅读


    上一篇：“杀富济贫，惩恶扬善”的强盗逻辑

    下一篇：自控力共读第5天（从微小的行动开始设定目标）