// Climbing Stairs | How to Write 1D Recurrence Relations

// tc = O(n)

// sc = O(n) --> stack space

import java.util.*;

public class dp {

    public static int func(int index) {

        if (index == 0) return 1;

        if (index == 1) return 1;

        int left = func(index - 1);

        int right = func(index - 2);

        return left + right;

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of stairs: ");

        int n = scanner.nextInt();

        int ways = func(n);

        System.out.println("Number of ways to climb " + n + " stairs: " + ways);

    }

}