Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? Note: given n is a positive integer.

Solution 1: If this is a junior high school math problem, I think I can solve it quickly, now to force buckle is not a thought. Maybe he’s getting dumber as he gets older. A closer look at the mathematics reveals Fibonacci numbers.

Fibonacci sequence: f(0)=0, F (1)=1, f(n) = F (n-1)+f(n-2). The code can be written directly as a sum of Fibonacci numbers.

Solution 2: Dynamic programming

public int climbStairs(int n){
    int[] dp = new int[n+2];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i < n; i++) {
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp[n];
}
Copy the code

The code is written to conform to the Fibonacci sequence, so dp[0] is not assigned, and it is more reasonable to set the length to N +2 when creating a new dp sequence. The for loop also starts at the third step. So in this case dp[I], the subscript of the array is the level of the ladder, the value of the array is the level of the ladder and there are several ways to do that. For example, the way to get up the third rung is the same thing as the way to get up the second rung plus the way to get up the first rung, and the way to get up the fourth rung is the same thing as the way to get up the third rung plus the way to get up the second rung.

I always feel that the problem of dynamic programming is completely out of my mind without looking at the solution of the problem, and I still do not fully understand the idea of dynamic programming. Before August to understand the dynamic programming this point, but also to brush some problems in this area.