Count ways to climb stairs

Summary

Count the number of distinct ways to climb n stairs taking 1 or 2 steps at a time using dynamic programming.

Problem statement

You are climbing a staircase that has n steps. You can take either 1 step or 2 steps at a time. How many distinct ways are there to reach the top? For example: - If n = 1, there is 1 way: [1] - If n = 2, there are 2 ways: [1+1], [2] Requirements: - Implement climb_ways(n) where n is a non-negative integer. - Return the number of distinct ways to climb to the top using 1- or 2-step moves. - Use dynamic programming (memoization or tabulation) for efficiency. - Define climb_ways(0) = 1 (one way: take no steps). - For negative n, raise a ValueError.

Task

Implement climb_ways(n) that returns how many distinct sequences of 1- and 2-step moves reach the top of n stairs using memoization or tabulation.

Examples

Input format

A single non-negative integer n passed as an argument to climb_ways(n).

Output format

An integer: the number of distinct ways to reach step n using 1- and 2-step moves.

Constraints

0 <= n <= 1000. Result grows exponentially but fits in Python int for typical interview ranges. Use DP to achieve O(n) time and O(1) or O(n) space.

Samples