Blind 75
Climbing Stairs
- Problem
- LC 70
- Category
- DP
- File
- blind75_LC70ClimbingStairs.java
- Path
- pkg5leetcode/blind75/blind75_LC70ClimbingStairs.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC70ClimbingStairs.java
- Approach
- Fibonacci DP; ways(n) = ways(n-1) + ways(n-2).
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Climbing Stairs | LC 705 * APPROACH: Fibonacci DP; ways(n) = ways(n-1) + ways(n-2).6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class blind75_LC70ClimbingStairs {9 static int climbStairs(int n) {10 if (n <= 2) return n;11 int a = 1, b = 2;12 for (int i = 3; i <= n; i++) {13 int c = a + b;14 a = b;15 b = c;16 }17 return b;18 }19 20 public static void main(String[] args) {21 check(climbStairs(2) == 2, "case1");22 check(climbStairs(3) == 3, "case2");23 System.out.println("all tests passed");24 }25 26 static void check(boolean cond, String name) {27 if (!cond) throw new AssertionError("FAILED: " + name);28 System.out.println(" PASS " + name);29 }30}