This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

The title

Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each subsequent digit is the sum of the first two digits. That is:

F (0) = 0, F (1) = 1, F (n) = F (n - 1) + F (n - 2), where n > 1Copy the code

Here’s n. Please calculate F(n).

The sample

Input: 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1 Input: 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2 Input: 4 Output: 3 Explanation:  F(4) = F(3) + F(2) = 2 + 1 = 3Copy the code

prompt

  • 0 <= n <= 30

Their thinking

According to the problem, starting with the number 2, each number is the sum of the first two numbers. So, here we can get two ways to solve the problem:

  • Top down: FromF(n)Set out and went to0In the direction of

  • Bottom up: from0Let’s go and derive thisF(n)

Code implementation

Method one: recursion

class Solution {
    public int fib(int n) {
        // Boundary judgment
        if(n < 2) {return n;
        }
        // Recurse downward to get the final result
        return fib(n - 1) + fib(n - 2); }}Copy the code

Method two: recursive optimization

Although method 1 is simple, it will produce repeated calculations in the recursion process. Here, we can use a Map to save the calculation results of each time. When the calculated value is encountered, we can directly return it from the Map.

class Solution {
    private Map<Integer, Integer> map = new HashMap<>();
    public int fib(int n) {
        // Boundary judgment
        if(n < 2) {return n;
        }
        // Check whether the current value has recursed, if so, return the result directly
        if(map.containsKey(n)){
            return map.get(n);
        }
        // Recurse downward to get the final result
        int sum = fib(n - 1) + fib(n - 2);
        // Save the result
        map.put(n, sum);
        returnsum; }}Copy the code

Method 3: Dynamic specifications

class Solution {
    public int fib(int n) {
        // Boundary judgment
        if(n < 2) {return n;
        }
        
        int[] dp = new int[n + 1];
        / / initialization
        dp[1] = 1;
        // Add the sum of the first two numbers
        for(int i = 2; i <= n; ++i){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        // Return the result
        returndp[n]; }}Copy the code

Method 4: Dynamic specification optimization

In method three, we define an array of length n, and the actual calculation only uses the two elements before I, so we can define two variables to hold the first result and omit the rest.

class Solution {
    public int fib(int n) {
        // Boundary judgment
        if(n < 2) {return n;
        }
        
        int front = 0, after = 1, tmp;

        for(int i = 2; i <= n; ++i){
            // Update the status
            tmp = after;
            after += front;
            front = tmp;
        }

        returnafter; }}Copy the code

The last

The article has the bad place that writes, ask big guy people not stingy give instruction, mistake is most can let a person grow, wish I and big guy the distance between shorten gradually!

If you think the article is helpful to you, please like, collect, follow, comment one key four connect support, your support is my creation biggest power!!

Source: leetcode-cn.com/problems/fi…