Wspinanie się po schodach i kombinacje monet
Klasyczne rekurencje jednowymiarowe od podstaw
Wspinanie się po schodach i kombinacje monet to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Poznaj problem schodów
Można pokonywać po 1 lub 2 stopnie naraz. Na ile sposobów można dotrzeć do stopnia n? To klasyczne DP 1D jest po prostu Fibonaccim w przebraniu.
Znajdź rekurencję
Na stopień i można wejść ze stopnia i-1 albo i-2. Zatem dp[i] = dp[i-1] + dp[i-2], sumując oba ostatnie ruchy.
dp[i] = dp[i-1] + dp[i-2]Ustal przypadki bazowe
Istnieje jeden sposób, aby pozostać na ziemi, i jeden sposób, aby dotrzeć na stopień 1. Te przypadki bazowe dają początek całej tabeli.
dp[0], dp[1] = 1, 1Wypełnij tabelę i odczytaj wynik
Wystarczy przechodzić w górę, a ostatnia komórka będzie zawierać wynik. Całe rozwiązanie to niewielka pętla tabulacji.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Ogranicz do dwóch zmiennych
Potrzebne są tylko dwie ostatnie wartości, więc można usunąć tablicę. Ta wersja ze złożonością pamięciową O(1) jest ulubionym rozwiązaniem na zawodach.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bPrzejdź do kombinacji monet
Mając dane nominały monet, należy policzyć, na ile sposobów można uzyskać kwotę A. Kolejność nie ma tu znaczenia, więc liczymy kombinacje, a nie sekwencje.
coins = [1, 2, 5]Tabela kombinacji
Niech dp[x] oznacza liczbę sposobów utworzenia kwoty x. Należy zacząć od jednego sposobu uzyskania zera: zbioru pustego monet.
dp = [0]*(A+1)
dp[0] = 1Umieść pętlę monet na zewnątrz
Należy umieścić pętlę po monetach na zewnątrz pętli po kwotach. Taka kolejność zlicza każdą kombinację dokładnie raz, a nie wszystkie permutacje.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Kombinacje a permutacje
Po zamianie kolejności pętli będą Państwo liczyć uporządkowane sposoby. Samo zagnieżdżenie pętli zmienia znaczenie wyniku.
Wariant minimalnej liczby monet
Aby znaleźć najmniejszą liczbę monet, należy przechowywać minimum zamiast sumy. Tablicę trzeba zainicjalizować wartością nieskończoności i dodawać 1 do najlepszego rozwiązania podproblemu.
dp[x] = min(dp[x], dp[x-c] + 1)Jeden schemat, wiele zastosowań
Schody i monety mają wspólną strukturę: każdy stan sumuje wartości kilku poprzednich stanów albo wybiera spośród nich minimum. Gdy rozpoznają Państwo ten schemat, kod pisze się niemal sam.
Szybkie sprawdzenie
Podczas zliczania kombinacji monet, jaka kolejność pętli pozwala uniknąć duplikatów?
Podsumowanie: sumuj ostatnie ruchy
Potrafią już Państwo rozwiązywać problem schodów i zliczania monet za pomocą rekurencji 1D. Każdy wynik jest sumą kilku wcześniejszych stanów, a kolejność pętli rozstrzyga, czy liczymy kombinacje, czy permutacje.
Ucz się Python dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 30
- Lekcje
- 120
Często zadawane pytania
Czy lekcja „Wspinanie się po schodach i kombinacje monet” jest bezpłatna?
Tak — pełny tekst „Wspinanie się po schodach i kombinacje monet” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Wspinanie się po schodach i kombinacje monet”?
Klasyczne rekurencje jednowymiarowe od podstaw Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Wspinanie się po schodach i kombinacje monet”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Memoizacja kontra tabulacja
- Definiowanie stanu i przejścia
- Wspinanie się po schodach i kombinacje monet
- Najdłuższy rosnący podciąg