The count for step n equals the sum of the counts for steps n-1 and n-2, following the Fibonacci pattern.

Climbing Stairs

easy

Acceptance: 62%

Dynamic Programming

A staircase has n steps. On each move you may ascend either one step or two steps. Calculate how many distinct sequences of moves will bring you from the ground to the top.

Examples

Example 1:

Input:n = 4

Output:5

Explanation: The five ways are: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2.

Example 2:

Input:n = 5

Output:8

Explanation: There are eight distinct sequences of 1-step and 2-step moves.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Climbing Stairs

Examples

Hints

Related Problems