State the base cases before writing the loop
For climbing stairs with steps of one or two, let ways[n] count ordered sequences reaching step n. The empty sequence gives ways[0]=1; ways[1]=1; later values satisfy ways[n]=ways[n-1]+ways[n-2].
fun stairs(n: Int): Long {
require(n in 0..91)
var previous = 1L
var current = 1L
if (n == 0) return previous
for (step in 2..n) {
val next = previous + current
previous = current
current = next
}
return current
}
The bound differs from Fibonacci because stair counts are shifted by one index. For minimum-cost climbing, replace counting with a minimum over predecessor cost plus the current step's cost, after explicitly defining allowed starting positions and whether the destination itself has a cost.
Exercise
Verify counts 1, 1, 2, 3, 5 for steps zero through four. Build a minimum-cost variant and hand-trace [10,15,20] under the usual start-at-zero-or-one convention, which yields 15.
Check: counting paths and minimizing cost share a state graph but use different aggregation operations.