Nuggets team number online, help you Offer impromptu! Click for details

preface

Yesterday we tried our first dynamic programming problem, the maximum sum divisible by three, using both full recursion and dynamic programming. Today’s clock-in problem is still a dynamic programming problem. Probably a lot of people when they do dynamic programming, climbing stairs is the first thing they do. But it’s still an interesting solution. So today we’re going to do it both recursively and dp.

Topic describes

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.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 + 2. 2Copy the code

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building. 1. 1 order + 1 order + 1 order 2. 1 order + 2 order 3Copy the code

Source: LeetCode link: leetcode-cn.com/problems/cl… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

If you looked at yesterday’s largest sum divisible by three, it should be easy to see that, if that was the advanced version of the problem, this is at best the elementary version. Now, the same idea, if I get to the NTH step, then I might get up from the n-1 step, or I might get up from the N-2 step.

If the total number of schemes of order n is denoted as f(n), then the total number of n-1 and n-2 is f(n-1) and F (n-2), respectively. From the above analysis, it is not difficult to see that f(n) = F (n-1) + f(n-2). I want to make sure my domain makes sense, so n minus 2 is greater than or equal to 1. We can get n∈[3, infinity), n= n *. For example, when less than 3, when n=1, there is only one scenario from 0 to 1, and when n=2, there are two scenarios from 0 to 2, namely two steps at a time or one step at a time.

Now look at the code for the recursive idea:

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return climbStairs(n - 1) + climbStairs(n - 2); }}Copy the code

The code is concise and easy to understand. It looks like a pretty neat solution, but in this violent recursion, he has two sons every time for n, n-1 and n-2, and if he keeps recurring until he has a node 5, then he has to recurse for that node 8 more times, because 2 and 1 are definite numbers, so for n, The total number of recursions is going to be 2n minus 2. So in terms of time complexity, efficiency is very low.

Let’s optimize this code. Given that f(n) = f(n-1) + f(n-2) and f(1) = 1, f(2) = 2, it is not difficult for me to get f(3) = f(1) + f(2). If we store f of 1 in a temporary variable temp1, f of 2 in a temporary variable temp2, f of 3 is equal to temp1 plus temp2, then we’re going to do something about it and let f of 2 occupy temp1, f of 3 occupy temp2. So all the way to the end f(n) = temp1 + temp2.

The final code

After a slight change in the last violent recursive code, the final code optimized in this way is O(n) time.

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        int temp1 = 1, temp2 = 2, f_n = 3;
        for (int i = 3; i < n; ++i) {
            temp1 = temp2;
            temp2 = f_n;
            f_n = temp1 + temp2;
        }
        returnf_n; }}Copy the code

conclusion

I’m new to dynamic programming, but dynamic algorithms give me the impression that violent recursion is possible without considering efficiency. As for how to optimize recursion, the last few problems I have done are to find the correct state between n and n-1, and then reverse from 1->n, using arrays or temporary variables or other data structures to store information, thus reducing the time complexity. Keep it up!