This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

I. Title:Fibonacci number

Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. Namely: F (0) = 0, F (1) = 1. F (n) = F (n – 1) + F (n – 2), where n > 1. I give you n, please calculate F(n).

Second, the parsing

This is a classic recursive problem, but if you do it recursively, you’re going to see a lot of repetitions. For example, when calculating F(4), F(4)=F(3)+F(2), F(3)=F(2)+F(1)… Obviously, F(2) is evaluated twice in this process. The recursive algorithm is 2 to the n.

When we look at the Fibonacci sequence generation rules, we can find that dynamic programming is used to solve the problem. Every F(n) is derived from F(n-1) and F(n-2), and dynamic programming is also a solution to the problem of “every state must be derived from the last state” (this can be distinguished from greedy algorithms, which only pursue the optimal solution at each step without considering the last state).

Dynamic programming (DP) has three elements: optimal substructure, state transition equation and boundary. In this case:

  • F(n-1) and F(n-2) are optimal substructures of F(n)
  • F(n) = F(n-1) + F(n-2) is the state transition equation
  • F(0) = 0 and F(1) = 1 are boundaries

After identifying the three elements, we also need to determine the traversal order. If you’re still going from N to 0, you’re still going to double count, so 0 to N should be used.

In the process of solving a problem, you may need to do a lot of debugging. By deriving dp arrays by example, it’s a little bit more intuitive to see if our deriving is consistent. So here, when N=10, dp array would be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Three, code,

class Solution {
    public int fib(int n) {
        int f0 = 0;
        int f1 = 1;
        if(n < 2) {return n;
        }
        for(int i = 2; i <= n; i++){
            f1 = f1 + f0;
            f0 = f1 - f0;
        }

        returnf1; }}Copy the code

70. Climbing stairs