青蛙怎么跳到对岸（0003）

题意

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

输入

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);

希望程设能过?