Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Climb the stairs

I’m actually solving for the NTH term of the Fibonacci series f(n) = F (n-1)+f(n-2).

Method 1: Brute force recursion

  1. Find the recursion formula, the violent recursion
  2. No cache, high time complexity, leetcode does not pass
/** * Recursively, without caching, time complexity is high. O(2^n) * * @return * @paramn */ public static int climbStairs1(int n) { if (n < 3) return n; return climbStairs1(n - 2) + climbStairs1(n - 1); }Copy the code

Method two: dynamic programming

Public static int climbStairs2(int n) {if (n < 3) {return n; if (n < 3) {return n; } int f1 = 1; int f2 = 2; int f3 = 0; for (int i = 3; i < n + 1; i++) { f3 = f1 + f2; f1 = f2; f2 = f3; } return f3; }Copy the code