0Pricing
Coding Interview Prep · Lekcja

Minimalna suma ścieżki z przeszkodami

Przenoszenie najlepszego kosztu między komórkami

Minimalna suma ścieżki z przeszkodami to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Od zliczania do kosztu

Teraz każda komórka przechowuje wartość, a celem jest znalezienie najtańszej trasy do rogu. Cel zmienia się ze zliczania ścieżek na minimalizowanie kosztu.

Zdefiniuj stan

Niech dp[i][j] oznacza najmniejszy łączny koszt dotarcia do komórki (i, j). Ta sama siatka i te same ruchy, ale zamiast liczby ścieżek śledzimy sumy.

Przejście

Należy wybrać tańszego z dwóch sąsiadów, z których można nadejść, a następnie dodać wartość bieżącej komórki. Ten wybór funkcji min stanowi sedno rekurencji.

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Oznacz przeszkody

Przeszkoda to komórka, na której nie można stanąć. Należy przypisać jej koszt równy nieskończoności, aby żadna przechodząca przez nią ścieżka nie mogła być najtańsza.

INF = float('inf')

Obsłuż blokadę

Gdy siatka oznacza komórkę jako zablokowaną, wystarczy ustawić jej dp na nieskończoność i przejść dalej. Operacja min w naturalny sposób ją ominie.

if blocked(i, j):
    dp[i][j] = INF
    continue

Zabezpiecz punkt początkowy

Jeśli sama komórka początkowa jest zablokowana, żadna ścieżka nie istnieje. Należy sprawdzić to najpierw, aby nie zwrócić bezsensownego kosztu.

Zainicjalizuj pierwszą komórkę

Komórka początkowa nie ma sąsiadów, z których można do niej nadejść, więc jej koszt jest równy jej własnej wartości. Należy ustawić dp[0][0] przed rozpoczęciem pętli.

dp[0][0] = grid[0][0]

Obsłuż krawędzie

W górnym wierszu wartości napływają tylko z lewej, a w lewej kolumnie tylko z góry. Należy obsłużyć te krawędzie, aby nigdy nie odczytywać wartości spoza siatki.

Nieskończoność się propaguje

Dodanie wartości do nieskończoności nadal daje nieskończoność, dlatego całkowicie odcięta komórka zachowuje koszt INF. Komórki nieosiągalne oznaczają się automatycznie.

Odczytaj wynik

Minimalny koszt znajduje się w prawej dolnej komórce. Jeśli ta wartość nadal wynosi nieskończoność, żadna poprawna ścieżka nie istnieje.

ans = dp[m-1][n-1]
if ans == INF:
    ans = -1

Kiedy zachłanność zawodzi

Ciągłe wybieranie mniejszego sąsiada może prowadzić do pułapki. Tylko pełne DP gwarantuje globalnie najtańszą ścieżkę, a nie zachłanne spojrzenie na najbliższy krok.

Szybkie sprawdzenie

Jak sprawić, aby DP dla ścieżek omijało zablokowaną komórkę bez osobnego obsługiwania każdego sąsiada?

Podsumowanie: najtańsza ścieżka z przeszkodami

Należy wybrać tańszego sąsiada, dodać wartość komórki, ustawić zablokowane komórki na nieskończoność i odczytać wartość w rogu. INF w tym miejscu oznacza brak ścieżki. 🧱

Często zadawane pytania

Czy lekcja „Minimalna suma ścieżki z przeszkodami” jest bezpłatna?

Tak — pełny tekst „Minimalna suma ścieżki z przeszkodami” 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Minimalna suma ścieżki z przeszkodami”?

Przenoszenie najlepszego kosztu między komórkami Ćwiczysz Coding Interview Prep 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ąć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 2 z 4.

Ile czasu zajmuje lekcja „Minimalna suma ścieżki z przeszkodami”?

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 Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep 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

  1. Zliczanie ścieżek na siatce
  2. Minimalna suma ścieżki z przeszkodami
  3. Najdłuższy wspólny podciąg
  4. Odległość edycyjna krok po kroku
← Powrót do Coding Interview Prep