青蛙怎么跳到对岸(0003)

发布时间:2023年12月21日

题意

给定多块石头,每一块石头上面有一个数字,表示最多可以从这块石头往前面跳多远。问最少跳多少次可以到最后一块石头

输入

2 3 1 1 4

输出

2

说明

从第一块石头跳到第二块,然后跳到最后一块,两次跳跃,是最少跳跃次数

代码

#include<bits/stdc++.h>

using namespace std;

int solve(vector<int> &s)
{
	int n=s.size();
	vector<int> dp(n,n);
	
	dp[0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n&&j<=i+s[i];j++)
		{
			dp[j]=min(dp[j],dp[i]+1);
		}
	}
	
	return dp[n-1];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	vector<int> s;
	int a;
	while(cin>>a)
	{
		s.push_back(a);
	}
	
	cout<<solve(s)<<endl;
	
	return 0;
}

总结

1.动态规划

dp数组表示的是到达某一块石头需要用的最小跳跃次数,先把dp数组初始化为n,表示到达每一块石头需要n次跳跃(这和把最大值设为很小,把最小值设为很大是一个道理,方便更新dp的数值),然后把第一个dp的数值初始化为0,表示到达第一块石头不需要进行跳跃

遍历每一块石头,从该石头后一块石头开始遍历是第二层循环,设置限制条件,每一次跳跃最多跳跃s[i]个单位,dp[i]+1表示的是从上一次结束跳跃的位置再进行一次跳跃

2.vector

因为没有给定数据范围,所以使用动态数组,使用数组的时候要引用地址(普通变量有时也要引用),往容器里面添加元素,使用这个

s.push_back(a);

希望程设能过?

文章来源:https://blog.csdn.net/L3102250566/article/details/135127723
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。