public class Main {

    static class FibonacciClimbingStairs {
        static int[] memo = new int[46];

        public int climbStairs(int n) {
            return climbTabularizedSpaceOptimized(n, 2);
        }

        private int climbMemoized(int n, int k) {
            if (n == 0) return 1;

            if (memo[n] != 0) return memo[n];

            int ways = 0;

            for (int jump = 1; jump <= k; jump++) {
                if (n - jump >= 0) {
                    ways += climbMemoized(n - jump, k);
                }
            }

            memo[n] = ways;
            return ways;
        }

        private int climbTabularized(int n, int k) {
            int[] tab = new int[n + 1];
            tab[0] = 1;

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= k; j++) {
                    if (i - j >= 0) {
                        tab[i] += tab[i - j];
                    }
                }
            }
            return tab[n];
        }

        private int climbTabularizedSpaceOptimized(int n, int k) {
            int[] dp = new int[k];
            dp[0] = 1;

            for (int i = 1; i <= n; i++) {
                int sum = 0;

                for (int j = 1; j <= k; j++) {
                    if (i - j >= 0) {
                        sum += dp[(i - j) % k];
                    }
                }

                dp[i % k] = sum;
            }

            return dp[n % k];
        }
    }

    public static void main(String[] args) {
        FibonacciClimbingStairs sol = new FibonacciClimbingStairs();

        // basic tests
        for (int n = 0; n <= 10; n++) {
            System.out.println("n = " + n + " -> " + sol.climbStairs(n));
        }

        // expected:
        // 0 -> 1
        // 1 -> 1
        // 2 -> 2
        // 3 -> 3
        // 4 -> 5
        // 5 -> 8
    }
}