-
Notifications
You must be signed in to change notification settings - Fork 4
/
ClimbingStairs.java
66 lines (61 loc) · 1.56 KB
/
ClimbingStairs.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package algorithms;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
/**
* 70. Climbing Stairs
* https://leetcode.com/problems/climbing-stairs/
* Difficulty : Easy
* Related Topics : Math, Dynamic Programming, Memoization
*
* You are climbing a staircase. It takes n steps to reach the top.
*
* Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
*
* Example 1:
*
* Input: n = 2
* Output: 2
* Explanation: There are two ways to climb to the top.
* 1. 1 step + 1 step
* 2. 2 steps
*
* Example 2:
*
* Input: n = 3
* Output: 3
* Explanation: There are three ways to climb to the top.
* 1. 1 step + 1 step + 1 step
* 2. 1 step + 2 steps
* 3. 2 steps + 1 step
*
* Constraints:
*
* 1 <= n <= 45
*
* created by Cenk Canarslan on 2021-11-24
*/
public class ClimbingStairs {
@Test
public void testClimbingStars() {
assertEquals(5, climbStairs(4));
assertEquals(3, climbStairs(3));
assertEquals(8, climbStairs(5));
}
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Climbing Stairs.
* Memory Usage: 37.7 MB, less than 21.29% of Java online submissions for Climbing Stairs.
*
* hint: it's almost the same as Fibonacci Numbers
*/
public int climbStairs(int n) {
if (n < 1 || n > 45) return -1;
if (n <= 2) return n;
int[] c = new int[n];
c[0] = 1;
c[1] = 2;
for (int i = 2; i < n; i++) {
c[i] = c[i-1] + c[i-2];
}
return c[n-1];
}
}