1. Title Description

A frog can jump up at a time 1 Stepped steps , You can jump on it 2 Stepped steps . Ask the frog to jump on one n How many jumps are there in the steps .

The answer needs to be modelled 1e9+7（1000000007）, If the initial result of calculation is ：1000000008, Please return 1.

Example 1：

Input ：n = 2
Output ：2

Example 2：

Input ：n = 7
Output ：21

Example 3：

Input ：n = 0
Output ：1

Tips ：

0 <= n <= 100

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving steps of dynamic programming

2.1.dp[i] The definition of

For the above question , Let's give a number , Such as 8, that dp[8] It means that the Frog 8 The jumping of steps , that dp[i] It means that the Frog i The jumping of steps .

2.2. recursion

For this question , We can think like this , The frog will jump to i Where did the level jump from , Because frogs can jump one or two levels , So jump to i Level may be from i - 1 It jumped from the first level , It could be from i - 2 It jumped from the first level , So jump to i The jumping method of level is dp[i - 1] + dp[i - 2], The recursion is dp[i] = dp[i - 1] + dp[i - 2];

2.3.dp Initialization and recursive function exit

I have a doubt , Why jump on 0 The next step is 1 Jump ....... ha-ha

because i==0 perhaps i == 1 Time is not enough to be recursive , So we have to give the initial value dp[0] = 1,dp[1] = 1, These initializations are the exits of recursive functions .

2.4. Recursive function

int dp(int n) {
    
	if(n < 2){
    
		return 1;// exit , Where to initialize 
	}

	return (dp(n - 1) + dp(n - 2))  % 1000000007;
}

2.5. Change recursion to iteration

Why change to iteration ？ And look at the picture ？

As can be seen from the recursive tree , Recursion does a lot of repetitive things , The time complexity is exponential , So instead of iterating , Use an array to record the calculated data , Then you can use it directly when you need it in the future , Instead of double counting .

int dp(int n) {
    
	if(n < 2) {
    
		return n;
	}
	vector<int> dp(n, 0);// Don't consider 0, consider 0 If so, initialize to dp(n + 1, 0)
	dp[0] = 1;
	dp[1] = 2;
	for(int i = 2;i < n;i++) {
    
		dp[i] = (d[i - 1] + dp[i - 2]) % 1000000007;
	}

	return dp[i - 1];
}

2.6. Iterative optimization

Because calculation dp(n), Just need to know dp(n-1) and dp(n-2) Just fine , So we only need to use two variables to save dp(n-1)、dp(n-2) that will do

int dp(int n) {
    
	int f1 = 1;
	int f2 = 1;
	for(int i = 2;i <= n;i++) {
    
		int f3 = (f1 + f2) % 1000000007;
		f1 = f2;
		f2 = f3;
	}

	return f2;
}

3. Conclusion

That's not the point . I don't see any effect , Because this question can be seen by the naked eye .