Let’s start with the classic sample: Climbing stairs:

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. 2 copy codeCopy 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

Function signature:

public static int climbStairs(int n) {}
Copy the code

The simplest. – Brute force

Dp is basically the derivation of the recursion.

Assuming there are n steps ahead (n is large enough), then one or two steps can be taken. The choice between these two steps is different, so the path at the current level is:

Take one step + take two steps

The result of taking one step and two steps can also be broken down into one more step and two steps… Several combinations of.

Then the results of the current layer are not concerned with the results of the lower layer, so the recursive formula can be obtained:

F of n is F of n-1 plus F of n-2.

So at the end of the day, you just add termination conditions, and you have a solution.

It is easy to obtain termination conditions:

  • There are no steps ahead. It’s a way to go
  • There is also a step in front, which is also a way to go

That is:

if(n <= 1) return 1;

So here’s the simplest solution:

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

The result of submitting on LeetCode is a timeout, the idea is correct.

Brute Force 2.0 – Keep a record for each level

Brute force cracking has timed out, so is there any way to optimize the time complexity?

According to the above solution, according to the nature of iteration, it can be easily deduced that the final result is several F(0)+F(1)+F(2)+… .

If you save the result that you calculated when you had n layers left, so that you don’t have to calculate it the next time, you can save some time.

According to this idea, there is the following solution:

private static List<Integer> mo = new ArrayList<>();

    public static int climbStairs(int n) {
        if(mo.size()==0){
            mo.add(1); mo.add(1);
        }
        if(n <= 2) return mo.get(n);
        if(mo.size()>n) return mo.get(n);
        int cur = climbStairs(n-1)+climbStairs(n-2);
        mo.add(cur);
        return cur;
    }
Copy the code

Here we are storing known records in an indeterminate array. The end result:

Execution time: 0 ms, beating 100.00% of users in all Java commits

Memory consumption: 35.2 MB, beating 43.89% of all Java commits

In DP this method is also called memo.

Brute Force 3.0 – Memo Slimmer

This is further simplified using arrays and local variable arrays

It can be known from n:

  • In fact, the size of an array is determined to be n+1(n+1 numbers from 0 to n). You can use arrays instead of arrayLists to save time for expansion and function calls

This way, however, you can’t record memos through global variables, either by creating a new method or by using loops instead of iterations.

By using loops here, you can also avoid StackOverflow problems.

  • Loop idea:
    • Easy to see: we only need the NTH order result, so return dp[n].
public static int climbStairs(int n) {
    int[] dp = new int[n+1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp[n];
}
Copy the code

Slim memos down with scrolling arrays

According to the above array method, we get a revelation:

  • We really only care about the values of F(n-1) and F(n-2), so we use three variables to represent F(n),F(n-1),F(n-2), down in the body of the cyclerollingAnd can achieve the same effect.
    • This method is called scrolling arrays.
    public static int climbStairs(int n) {
        int curRes = 1,ancestor = 1,prev = 1;
        for (int i = 2; i <= n; i++) {
            curRes = ancestor + prev;
            ancestor = prev;
            prev = curRes;
        }
        return curRes;
    }
Copy the code

So this is the best way to solve this problem by DP.

Conclusion:

  • The most important thing in DP is the formula that we derive from the beginning.
  • Use memos to record information, and if possible, use scroll arrays instead of arrays for space optimization.