Leetcode skimming -- bit by bit record 017

17. The finger of the sword Offer 10-II. The problem of frog jumping on the steps

requirement

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.

Ideas

Let's jump up n The steps have f(n) Jump . Of all the jumps , There are only two situations for the frog's last step ： Jump on 1 Grade or 2 Stepped steps .

• Situation 1 ： When it comes to 1 Stepped steps , Remnant n-1 A stair , There are a total of f(n-1) Jump ;
• Situation two ： When it comes to 2 Stepped steps , Remnant n-2 A stair , There are a total of f(n-2) Jump .
  namely f(n) Is the sum of the above two situations , f(n)=f(n-1)+f(n-2) , The above recurrence property is Fibonacci sequence . however , The problem of frog jumping on the steps ： f(0)=1 , f(1)=1 , f(2)=2.

Problem solving

#include <iostream>
using namespace std;
#include <vector>

class Solution {
    
public:
    int numWays(int n) {
    
        if (n == 0) {
    
            return 1;    //  If you ask  f(0)  Then return directly  1 , initialization  f(0)
        }
        vector<int> dp(n + 1, 1);  //  initialization  dp  list 
        dp[1] = 1;                 //  initialization  f(1)
        for (int i = 2; i <= n; i++) {
    
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;  //  State transition calculation  f(2), f(3), ..., f(n) 
        }
        return dp[n];  //  return f[n]
    }
};

void test01()
{
    
    Solution s;
    for (int i = 0; i < 10; i++) {
    
        int n = s.numWays(i);
        cout << n << " ";
    }
    cout << endl;

}

int main()
{
    
    test01();

    system("pause");
    return 0;
}

I hope this article can help you , If there is anything wrong with the above , Welcome to correct

Sharing determines the height , Learn to widen the gap