Climbing Stairs and 1-D DP

DSA · Dynamic Programming

Theory

One-dimensional DP problems have a state that depends on a single index, such as "the number of ways to reach step i" or "the best amount robbed up to house i". Each answer is computed from a few previous answers, so only the last few values need to be kept, reducing space to O(1). Climbing stairs (1 or 2 steps) follows ways(i) = ways(i-1) + ways(i-2); house robber follows best(i) = max(best(i-1), best(i-2) + value[i]).

Why we use it

1-D DP patterns appear in many interview problems and show how to turn a recurrence into a fast loop.

When to use it

Use it for counting paths with step choices, maximising non-adjacent picks, decoding messages, minimum cost to reach the end, and similar linear problems.

How it works

  1. ways[0] = 1, ways[1] = 1
  2. For i = 2..n
  3. ways[i] = ways[i-1] + ways[i-2]
  4. Return ways[n]

Syntax

ways[0] = ways[1] = 1
ways[i] = ways[i-1] + ways[i-2]

best[i] = max(best[i-1], best[i-2] + v[i])
Time: O(n)   Space: O(1) with two variables

Example

def climb(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def house_robber(values):
    prev, cur = 0, 0
    for v in values:
        prev, cur = cur, max(cur, prev + v)
    return cur

def min_cost_stairs(cost):
    a = b = 0
    for c in cost:
        a, b = b, min(a, b) + c
    return min(a, b)

print("Ways to climb 10 stairs:", climb(10))
print("Best robbery from [2,7,9,3,1]:", house_robber([2, 7, 9, 3, 1]))
print("Min cost stairs:", min_cost_stairs([10, 15, 20]))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic