Climbing Stairs: the idea to remember.

The core insight

Ways to reach a step equal ways to reach the previous step plus ways to reach the step before that.

Why it works

Every valid path ends in either a one step move or a two step move, and those cases are disjoint.

The mistake to avoid

Use ways(0)=1 for the empty prefix so the first two states follow the recurrence cleanly.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int climbStairs(int n) {
    int before = 1, current = 1;
    for (int step = 2; step <= n; step++) {
        int next = before + current;
        before = current;
        current = next;
    }
    return current;
}

Make the next connection