博客

题目：



本题是一个简单的dp问题，只需要知道表达式dp[i + j] = std::min(dp[i] + 1, dp[i + j]);就行了，这道题我唯一的迷惑就是不知道跳上第一个木桩算不算一次，这里涉及到dp[0]的取值。如果按照所给答案等于4来看的话，就算一次弹跳了。个人感觉这道题题意给得不够明确。

#include<iostream>
#include<algorithm>
#include<vector>

using std::cin;
using std::cout;
using std::endl;
int main()
{
	int n, dis;
	std::vector<int>distance;
	cin >> n;
	for (auto i = 0; i < n; i++) {
		cin >> dis;
		distance.push_back(dis);
	}
	std::vector<int>dp(n + 1, INT_MAX);
	//这道题不知道到第一个木桩是不是算一次，如果按照题目所给答案来看的话，dp[0] = 1，但题目没有明确给出说明，只能这样理解了。
	dp[0] = 1;
	for (auto i = 0; i < n; i++) {
		for (auto j = 1; j <= distance[i]; j++) {
			if(i + j <= n)dp[i + j] = std::min(dp[i] + 1, dp[i + j]);
		}
	}
	cout << dp[n - 1] << endl;
	return 0;
}