Solve the kangaroo crossing problem (DP)

Problem description : A kangaroo wants to jump from one side of the river to the other , The river is wide , But there are many piles in the middle of the river , There is one every other meter , There is a spring on each pile , Kangaroo can jump farther by jumping on the spring . Each spring has a different force , Use a number to represent its power , If the force of the spring is 5, It means that kangaroos jump the most next   Can jump 5 rice , If 0, It means that you will fall into it and can't continue to jump . The river has a total of n Meters wide , Kangaroo is initially on the first spring , If you jump to the last spring, you'll cross the river , Given the force of each spring , How many jumps does the kangaroo need at least to reach the opposite bank . If you can't get to , Output one 1.

Input description : The input is divided into two lines , The first 1 The row is the length of the array n(1≤n≤10000), The first 2 Line is every - Item value , Separate... With spaces .

Output description : Output the least hops , If output one cannot be reached 1.

sample input ：

5 

2 0 1 1 1

sample output ：

4

Ideas ： A classic linear dp problem , You can define States f[i] For from 1 Go to the i The least jump , Then the state transition equation can be obtained as f[i] = min(f[i], f[j] + 1) (j < i && j + h[j] >= i), The answer for f[n + 1].

The code is as follows ：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010;

int n, h[N], f[N];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
	
	memset(f, 0x3f3f3f3f, sizeof f);
	f[1] = 0;
	
	for(int i = 2; i <= n + 1; i ++ )
	for(int j = 1; j < i; j ++ )
	if(j + h[j] >= i) 
	f[i] = min(f[i], f[j] + 1);
	
	if(f[n + 1] == 0x3f3f3f3f) puts("-1");
	else printf("%d", f[n + 1]);
	
	return 0;
}

You can find , The complexity of the defined state transition equation is O(n^2), But another state transition equation can also be defined .f[i] For from i The least jump to the opposite bank , So the state transfer equation is f[i] = min(f[i], f[i + j] + 1]) (1 <= j <= h[i]), So the answer is f[1], And the time complexity is O(n + sum) (sum = h[1] + h[2] + …………h[n]), So we can choose the method with less time complexity according to the data range given by the topic .

The code is as follows ：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010;

int n, h[N], f[N];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
	
	for(int i = n; i >= 1; i -- )
	{
		f[i] = 1 << 30;
		if(h[i] != 0)
		for(int j = 1; j <= h[i]; j ++ )
		f[i] = min(f[i], f[i + j] + 1);
	}
	
	if(f[1] == 1 << 30) puts("impossible");
	else printf("%d", f[1]);
	
	return 0;
}
/*
14
2 1 2 3 0 0 5 5 1 1 1 1 13 14
*/