Climbing n stairs, one or two steps at a time — how many distinct ways are there to reach the top? Rather than re-deriving the answer for every n from scratch, build a table left to right: the answer for n is just the answer for n−1 plus the answer for n−2, already sitting in the table. Once that idea is clear, the whole table collapses into two rolling variables — same answer, constant space.
← Back to the Field Guiden ta zinapoyaga bir yoki ikki qadamda chiqish — tepaga chiqishning nechta xil yo'li bor? Har bir n uchun javobni qaytadan hisoblash o'rniga, jadvalni chapdan o'ngga to'ldiring: n uchun javob — jadvalda allaqachon turgan n−1 va n−2 javoblarining yig'indisi, xolos. Bu g'oya aniq bo'lgach, butun jadval ikkita rolling o'zgaruvchiga siqiladi — javob bir xil, xotira esa doimiy.
← Qo'llanmaga qaytishWatch the bars below: each new slot is built from the sum of the two bars just before it — once a slot is filled, it's never recomputed, only reused.
Quyidagi ustunlarga qarang: har bir yangi katakcha undan oldingi ikkita ustunning yig'indisidan quriladi — bir marta to'ldirilgan katakcha hech qachon qayta hisoblanmaydi, faqat qayta ishlatiladi.
dp with one slot per step, from 0 up to n.dp[1] = 1 and dp[2] = 2.i from 3 up to n, filling the table strictly left to right, one slot at a time.i, compute dp[i] = dp[i-1] + dp[i-2]. Because the table is filled in increasing order of i, both dp[i-1] and dp[i-2] are already sitting in the table by the time dp[i] needs them — nothing is recomputed, nothing is guessed.dp[n] holds the answer: the total number of distinct ways to climb all n stairs.dp[i] only ever touches the two most recent entries, dp[i-1] and dp[i-2] — every older entry is never read again. That observation is what later motivates replacing the whole table with two rolling variables (see Complexity).dp array yarating, 0'dan n'gacha.dp[1] = 1 va dp[2] = 2.ini 3'dan n'gacha yurgizing, jadvalni qat'iy ravishda chapdan o'ngga, bir vaqtning o'zida bitta katakcha to'ldirib boring.ida dp[i] = dp[i-1] + dp[i-2]ni hisoblang. Jadval ining o'sib boruvchi tartibida to'ldirilgani uchun, dp[i-1] va dp[i-2] ikkalasi ham dp[i]ga kerak bo'lgan paytda allaqachon jadvalda turibdi — hech narsa qaytadan hisoblanmaydi, hech narsa taxmin qilinmaydi.dp[n] javobni saqlaydi: barcha n ta zinapoyaga chiqishning jami xil yo'llari soni.dp[i]ni to'ldirish faqat eng so'nggi ikkita yozuvga — dp[i-1] va dp[i-2]ga — tegadi, undan oldingi har qanday yozuv boshqa hech qachon o'qilmaydi. Aynan shu kuzatuv keyinchalik butun jadvalni ikkita rolling o'zgaruvchiga almashtirishga turtki beradi (Murakkablik bo'limiga qarang).Time: O(n). Whether the full table or just two rolling variables are kept, the work is the same: one pass over i from 3 up to n, doing one addition per step. There's no nested loop and no repeated recomputation, so the total work scales linearly with n.
Space: O(n) with the array, O(1) with rolling variables. The straightforward version above stores every dp[i] in an array of length n+1, so memory use grows linearly with n. But step 8 already pointed out that filling dp[i] only ever needs the two most recent entries — everything before dp[i-2] is never touched again. So instead of an array, keep two plain variables, say prev2 and prev1, holding the last two answers, and slide them forward each iteration: the new value becomes prev1, and the old prev1 becomes the new prev2. That's the O(1)-space rolling-variable version — same recurrence, same time complexity, but constant extra memory no matter how large n gets.
Vaqt: O(n). To'liq jadval saqlansa ham, faqat ikkita rolling o'zgaruvchi saqlansa ham, ish bir xil: i bo'yicha 3'dan n'gacha bitta pass, har bir qadamda bitta qo'shish. Nested loop yo'q, qayta hisoblash yo'q, shuning uchun jami ish n'ga chiziqli proportsional o'sadi.
Xotira: array bilan O(n), rolling o'zgaruvchilar bilan O(1). Yuqoridagi to'g'ridan-to'g'ri versiya har bir dp[i]ni n+1 uzunlikdagi array'da saqlaydi, shuning uchun xotira sarfi n'ga chiziqli proportsional o'sadi. Lekin 8-qadamda allaqachon ta'kidlanganidek, dp[i]ni to'ldirish faqat eng so'nggi ikkita yozuvga muhtoj — dp[i-2]dan oldingi hech narsa boshqa hech qachon ishlatilmaydi. Shuning uchun array o'rniga oxirgi ikkita javobni saqlaydigan ikkita oddiy o'zgaruvchi, aytaylik prev2 va prev1, tuting va ularni har bir iteratsiyada oldinga suring: yangi qiymat prev1ga aylanadi, eski prev1 esa yangi prev2ga aylanadi. Bu — O(1)-xotirali rolling-o'zgaruvchi versiya: bir xil recurrence, bir xil vaqt murakkabligi, lekin n qanchalik katta bo'lmasin, doimiy qo'shimcha xotira.
dp[1] = dp[2] = 1 instead of dp[1] = 1, dp[2] = 2, or forgetting that reaching step 2 has two ways, not one. Fix: work out the first two answers by hand before writing any loop, and seed the table with exactly those values — every later entry inherits any mistake made here.ways(n) = ways(n-1) + ways(n-2) — with no memoization. It's correct, but it recomputes the same smaller subproblems over and over (the same call to ways(n-2) happens once inside ways(n-1)'s work and again as a direct call), so runtime blows up exponentially. Fix: either cache results with memoization, or build the answer bottom-up with a table so each subproblem is solved exactly once.range(3, n) instead of range(3, n+1). Fix: since range excludes its endpoint, the loop must go up to and include n, so the last table slot actually gets filled — otherwise dp[n] is left untouched at its initial value of 0, and the function returns 0 instead of the real answer.prev2 = prev1 on one line and prev1 = prev2 + prev1 on the next. The second line now reads the already-overwritten prev2 (which is really the old prev1), so the new prev1 ends up double the old one instead of following the real recurrence. Fix: compute both new values from the old ones in a single simultaneous step, e.g. prev2, prev1 = prev1, prev2 + prev1, so nothing gets overwritten before it's read.dp[1] = 1, dp[2] = 2 o'rniga dp[1] = dp[2] = 1 deb qo'yish, yoki 2-zinapoyaga yetishning ikkita yo'li borligini, bittasi emasligini unutish. Yechim: har qanday loop yozishdan oldin birinchi ikkita javobni qo'lda hisoblab chiqing va jadvalni aynan shu qiymatlar bilan urug'lantiring — keyingi har bir yozuv shu yerda qilingan har qanday xatoni meros qilib oladi.ways(n) = ways(n-1) + ways(n-2) — memoization'siz. Bu to'g'ri, lekin bir xil kichikroq subproblem'larni qayta-qayta hisoblaydi (ways(n-2)ga bo'lgan bir xil chaqiruv bir marta ways(n-1)ning ishi ichida, yana bir marta to'g'ridan-to'g'ri chaqiruv sifatida sodir bo'ladi), shuning uchun runtime eksponensial darajada o'sib ketadi. Yechim: natijalarni memoization bilan cache qiling, yoki jadval yordamida javobni pastdan boshlab quring, shunda har bir subproblem aynan bir marta yechiladi.range(3, n+1) o'rniga range(3, n) bilan loop qilish. Yechim: range o'z oxirgi nuqtasini o'z ichiga olmagani uchun, loop n'gacha va n'ni ham o'z ichiga olgan holda borishi kerak, shunda jadvalning oxirgi katakchasi haqiqatan ham to'ldiriladi — aks holda dp[n] boshlang'ich 0 qiymatida qolib ketadi, va funksiya haqiqiy javob o'rniga 0 qaytaradi.prev2 = prev1, keyingi qatorda prev1 = prev2 + prev1 deb yozish. Ikkinchi qator endi allaqachon qayta yozilgan prev2ni (bu aslida eski prev1) o'qiydi, shuning uchun yangi prev1 haqiqiy recurrence'ga ergashish o'rniga eskisining ikki barobariga aylanadi. Yechim: ikkala yangi qiymatni eskilaridan bitta bir vaqtdagi qadamda hisoblang, masalan prev2, prev1 = prev1, prev2 + prev1, shunda hech narsa o'qilishidan oldin qayta yozilmaydi.Restated: given an integer n representing a staircase of n steps, and a rule that each move climbs either 1 or 2 steps, return the number of distinct sequences of moves that reach exactly the top (step n).
ways(n) = ways(n-1) + ways(n-2). That's a recurrence hiding inside a staircase story.ways(n) calling ways(n-1) and ways(n-2) mirrors the recurrence exactly and gives a correct answer, but without caching, the same smaller values (like ways(n-2)) get recomputed from scratch every time they're needed — the call tree grows exponentially, roughly O(2ⁿ).dp array, seed the two base cases (dp[1] = 1, dp[2] = 2), and fill the rest left to right with dp[i] = dp[i-1] + dp[i-2]. Every subproblem is now solved exactly once — O(n) time, O(n) space.dp[i] only ever reads dp[i-1] and dp[i-2] — nothing further back is ever touched again, so keeping the whole array is wasted memory.prev2 and prev1, sliding them forward each iteration. Same recurrence, same O(n) time, but O(1) space.The bottom-up array version first, matching the table-filling idea above:
def climb_stairs(n):
# base cases: 1 step has exactly 1 way, 2 steps have exactly 2 ways
if n <= 2:
return n
# dp[i] = number of distinct ways to reach step i
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
# fill the table left to right -- each answer reuses the two before it
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
The optimized, final solution — same logic, O(1) space via two rolling variables:
def climb_stairs(n):
# base cases: 1 step has exactly 1 way, 2 steps have exactly 2 ways
if n <= 2:
return n
# prev2 = ways to reach two steps back, prev1 = ways to reach one step back
prev2, prev1 = 1, 2
for i in range(3, n + 1):
# compute both new values from the old ones in one step, so
# neither variable is overwritten before it's read
prev2, prev1 = prev1, prev2 + prev1
# prev1 now holds the answer for step n
return prev1
Qayta bayon: n ta zinapoyadan iborat zinapoyani ifodalovchi butun son n berilgan, har bir harakat 1 yoki 2 qadam ko'tariladi — tepaga (n-zinapoyaga) aynan yetib boradigan xil harakatlar ketma-ketliklari sonini qaytaring.
ways(n) = ways(n-1) + ways(n-2). Bu zinapoya hikoyasi ichiga yashiringan recurrence.ways(n)ning ways(n-1) va ways(n-2)ni chaqirishi recurrence'ni aynan aks ettiradi va to'g'ri javob beradi, lekin cache'siz, bir xil kichikroq qiymatlar (masalan, ways(n-2)) har safar kerak bo'lganda qaytadan boshidan hisoblanadi — chaqiruvlar daraxti eksponensial o'sadi, taxminan O(2ⁿ).dp array quring, ikkita base case'ni urug'lantiring (dp[1] = 1, dp[2] = 2), va qolganini chapdan o'ngga dp[i] = dp[i-1] + dp[i-2] bilan to'ldiring. Endi har bir subproblem aynan bir marta yechiladi — O(n) vaqt, O(n) xotira.dp[i]ni to'ldirish faqat dp[i-1] va dp[i-2]ni o'qiydi — undan uzoqroqdagi hech narsa boshqa hech qachon ishlatilmaydi, shuning uchun butun array'ni saqlash behuda xotira sarfi.prev2 va prev1 bilan almashtiring, har bir iteratsiyada ularni oldinga suring. Bir xil recurrence, bir xil O(n) vaqt, lekin O(1) xotira.Avval bottom-up array versiyasi, yuqoridagi jadval-to'ldirish g'oyasiga mos ravishda:
def climb_stairs(n):
# base cases: 1 step has exactly 1 way, 2 steps have exactly 2 ways
if n <= 2:
return n
# dp[i] = number of distinct ways to reach step i
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
# fill the table left to right -- each answer reuses the two before it
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Optimallashtirilgan, yakuniy yechim — bir xil mantiq, ikkita rolling o'zgaruvchi orqali O(1) xotira:
def climb_stairs(n):
# base cases: 1 step has exactly 1 way, 2 steps have exactly 2 ways
if n <= 2:
return n
# prev2 = ways to reach two steps back, prev1 = ways to reach one step back
prev2, prev1 = 1, 2
for i in range(3, n + 1):
# compute both new values from the old ones in one step, so
# neither variable is overwritten before it's read
prev2, prev1 = prev1, prev2 + prev1
# prev1 now holds the answer for step n
return prev1
ways(1) = 1, ways(2) = 2, while the classic Fibonacci sequence starts from F(1) = 1, F(2) = 1. Working through the values shows ways(n) equals F(n+1) — same shape, shifted by one position.dp[i-1] and dp[i-2] are already computed and sitting in the table (or held in the rolling variables) the moment dp[i] needs them — every subproblem gets solved exactly once, in order. Recursing downward from n without caching solves the same smaller subproblems repeatedly (ways(n-2) gets computed once as part of ways(n-1)'s work, and again as its own direct call), and that duplication compounds at every level, which is exactly the exponential blow-up bottom-up filling avoids.dp[i] = dp[i-1] + dp[i-2] only ever looks two steps back. Once dp[i] has been computed, dp[i-3] and everything before it is never read again by any future step, so keeping the entire array is wasted memory. Two variables that slide forward each iteration hold exactly the information the next step needs and nothing more, which is why space drops from O(n) to O(1) while the time complexity and the final answer stay exactly the same.ways(1) = 1, ways(2) = 2dan boshlanadi, klassik Fibonacci ketma-ketligi esa F(1) = 1, F(2) = 1dan boshlanadi. Qiymatlarni hisoblab chiqsak, ways(n) — F(n+1)ga teng ekanligi ko'rinadi: bir xil shakl, faqat bitta pozitsiyaga siljigan.dp[i-1] va dp[i-2]ning dp[i]ga kerak bo'lgan paytda allaqachon hisoblanib, jadvalda (yoki rolling o'zgaruvchilarda) turishini kafolatlaydi — har bir subproblem tartib bilan, aynan bir marta yechiladi. n'dan cache'siz orqaga rekursiya qilish bir xil kichikroq subproblem'larni qayta-qayta yechadi (ways(n-2) bir marta ways(n-1)ning ishi ichida, yana bir marta o'zining to'g'ridan-to'g'ri chaqiruvi sifatida hisoblanadi), va bu takrorlanish har bir darajada ko'payadi — bu aynan pastdan to'ldirish oldini oladigan eksponensial o'sish.dp[i] = dp[i-1] + dp[i-2] recurrence'i faqat ikki qadam orqaga qaraydi. dp[i] hisoblangach, dp[i-3] va undan oldingi hamma narsa boshqa hech qanday kelajakdagi qadam tomonidan hech qachon o'qilmaydi, shuning uchun butun array'ni saqlash behuda xotira. Har bir iteratsiyada oldinga suriladigan ikkita o'zgaruvchi keyingi qadamga aynan kerak bo'lgan ma'lumotni saqlaydi, ortiqchasi yo'q — shuning uchun xotira O(n)dan O(1)ga tushadi, vaqt murakkabligi va yakuniy javob esa aynan bir xilligicha qoladi.