Pascal's Triangle

Q: Jaka jest złożoność czasowa generowania trójkąta Pascala?

Budowanie każdego wiersza na podstawie wiersza powyżej zajmuje O(n²) czasu dla n wierszy, ponieważ trójkąt zawiera około n²/2 elementów, a każdy z nich powstaje w wyniku jednego dodawania. Jest to optymalne, ponieważ musisz zapisać każdy element wyniku. Poza miejscem zajmowanym przez wynik algorytm wykorzystuje O(1) dodatkowej pamięci.

Q: Jaki związek ma trójkąt Pascala ze współczynnikami dwumianowymi?

Wpis k w wierszu r , licząc oba od 0, to współczynnik dwumianowy C(r, k) , czyli liczba sposobów wybrania k elementów spośród r . Zasada, że każdy wpis jest sumą dwóch wpisów nad nim, to tożsamość C(r, k) = C(r-1, k-1) + C(r-1, k) . Dlatego też suma elementów w wierszu r wynosi 2^r .

Q: Czy potrafisz obliczyć jeden wiersz bez budowania wierszy powyżej?

Tak. Zacznij od 1 i obliczaj każdy kolejny element na podstawie poprzedniego: C(r, k) = C(r, k-1) × (r-k+1) / k . Mnoż najpierw, a dopiero potem dziel, aby wynik dzielenia był dokładny, i użyj 64-bitowej liczby całkowitej do iloczynu. Wiersz r wymaga wtedy czasu O(r) i nie wymaga obliczania żadnych innych wierszy.

Q: Dlaczego trójkąt Pascala jest problemem programowania dynamicznego?

Każdy wpis zależy od dwóch mniejszych podproblemów, czyli wpisów znajdujących się nad nim, a te podproblemy w dużej mierze się pokrywają: zwykła rekurencja oblicza je wciąż od nowa. Budowanie wierszy po kolei zapisuje każdy podproblem tylko raz i wykorzystuje go ponownie, co zmienia wykładniczą liczbę operacji w O(n²) .

ŁatweProgramowanie dynamiczne

+10

W trójkącie Pascala pierwszy wiersz to [1]. Każdy kolejny wiersz ma o jeden element więcej, zaczyna się i kończy na 1, a każdy znajdujący się pomiędzy nimi element jest sumą dwóch elementów leżących bezpośrednio nad nim. Otrzymujesz liczbę całkowitą numRows. Zwróć pierwsze numRows wierszy trójkąta, zaczynając od wiersza na samej górze. Każdy wiersz powinien być tablicą liczb całkowitych.

Funkcja

generate(numRows: integer) → integer-2d-array

numRowsinteger: ile wierszy trójkąta zbudować
Zwracainteger-2d-array: pierwsze numRows wierszy, zaczynając od górnego wiersza

Ograniczenia

1 ≤ numRows ≤ 30
Każdy wpis w pierwszych 30 wierszach mieści się w 32-bitowej liczbie całkowitej ze znakiem. Największy z nich to 77558760 i znajduje się w środku wiersza 30.

Przykłady

Wejście: numRows = 5
Wyjście: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Wyjaśnienie: Każdy element wewnętrzny dodaje do siebie dwa elementy znajdujące się nad nim. W czwartym wierszu 3 = 1 + 2 i 3 = 2 + 1. W piątym wierszu 4 = 1 + 3, 6 = 3 + 3 i 4 = 3 + 1.

Wejście: numRows = 1
Wyjście: [[1]]
Wyjaśnienie: Przy jednym wierszu trójkąt składa się tylko z jego wierzchołka, [1].

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz zbudować tylko ostatni wiersz w pojedynczej tablicy, aktualizując go w miejscu, wiersz po wierszu, zamiast zachowywać wcześniejsze wiersze? W którą stronę musi przebiegać pętla wewnętrzna i dlaczego?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Reguła definiująca trójkąt jest rekurencyjna: element to suma dwóch elementów w poprzednim wierszu. Obliczanie każdego elementu od początku powoduje wielokrotne ponowne obliczanie tych samych wartości, a ilość pracy podwaja się z każdym wierszem. Wiersze, które masz zwrócić, są dokładnie zapisanymi odpowiedziami na te mniejsze problemy, więc buduj trójkąt od góry i odczytuj każdy wiersz z poprzedniego.

Oblicz rekurencyjnie każdy element

Poprawne, ale nie kończy się na największych testach

Intuicja

Ponumeruj wiersze i pozycje w wierszu, zaczynając od 0. Definicja trójkąta przyjmuje postać funkcji: entry(row, col) ma wartość 1, gdy col wynosi 0 lub jest równe row, czyli na dwóch krawędziach, a w przeciwnym razie jest równe entry(row-1, col-1) + entry(row-1, col). Wywołaj ją dla każdej pozycji w każdym wierszu, a otrzymasz trójkąt. Jest to poprawne, ponieważ dokładnie odtwarza definicję.

Problemem jest liczba wywołań. Rekurencja kończy się dopiero na krawędziach, gdzie zwraca 1, więc obliczenie wpisu o wartości v wymaga około 2v wywołań. Suma wartości w wierszu r wynosi 2^r, więc obliczenie 30 wierszy wymaga łącznie około 2^31 wywołań, czyli ponad dwóch miliardów. Te same niewielkie wpisy są obliczane ponownie miliony razy: entry(2, 1) znajduje się pod niemal każdą wartością poniżej.

Algorytm

Napisz entry(row, col): zwróć 1, jeśli col wynosi 0 lub col jest równe row.
W przeciwnym razie zwróć entry(row-1, col-1) + entry(row-1, col).
Dla każdego row od 0 do numRows-1 zbierz entry(row, col) dla każdego col od 0 do row.
Zwróć listę wierszy.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Buduj każdy wiersz na podstawie wiersza powyżej

Intuicja

Wersja rekurencyjna wciąż odwołuje się do elementów wcześniejszych wierszy, a i tak budujesz te wiersze. Obliczaj więc wiersze po kolei, od góry do dołu, a gdy wypełniasz wiersz r, odczytuj potrzebne wartości bezpośrednio z wiersza r-1, który jest już gotowy. Obliczenie każdego elementu wymaga wtedy jednego dodawania. To programowanie dynamiczne w najprostszej postaci: tabela mniejszych wyników jest jednocześnie samym wynikiem.

Zacznij wiersz r od r + 1 jedynek, co ustawia oba brzegi. Następnie dla każdej wewnętrznej pozycji c od 1 do r-1 ustaw ją na above[c-1] + above[c]. Wiersze 0 i 1 nie mają pozycji wewnętrznych, więc pozostają równe [1] i [1, 1] bez specjalnego przypadku.

Trójkąt zawiera 1 + 2 + ... + n, czyli około n²/2 elementów, a obliczenie każdego zajmuje stały czas, więc złożoność obliczeniowa wynosi O(n²). Poza wynikiem, który i tak musisz zwrócić, metoda nie wymaga dodatkowej pamięci. Dla numRows = 30 oznacza to 465 elementów zamiast dwóch miliardów wywołań.

Algorytm

Zacznij od pustej listy wierszy.
Dla każdego row od 0 do numRows-1 utwórz row + 1 jedynek.
Dla każdej wartości col od 1 do row-1 ustaw ją na sumę wartości na pozycjach col-1 i col poprzedniego wiersza.
Dodaj wiersz i kontynuuj. Zwróć listę.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Pułapki i przypadki brzegowe

Pętle są krótkie, więc błędy dotyczą granic i pierwszych wierszy.

Zwracanie numRows + 1 wierszy. Jeśli numerujesz wiersze od 0, ostatni potrzebny wiersz to numRows-1.
Wykonywanie pętli wewnętrznej dla krawędzi. Pozycja 0 nie ma lewego elementu nadrzędnego, a pozycja row nie ma prawego elementu nadrzędnego, więc odczyt above[col-1] lub above[col] w tych miejscach wykracza poza zakres. Wypełniaj tylko pozycje od 1 do row-1.
Zapis zakresu, który zawodzi dla małych wierszy. Swiftowe 1..<row powoduje awarię, gdy row wynosi 0, a w R 2:(row-1) odlicza w dół do 1, gdy row wynosi 2. Zabezpiecz te przypadki albo ustaw początkowe pozycje wewnętrzne na jedynki, aby dla wierszy 0 i 1 nie była potrzebna pętla.
Obliczanie elementów za pomocą silni. C(29, 14) mieści się w typie int, ale 29! powoduje przepełnienie nawet 64-bitowej liczby całkowitej, więc wzór oparty na silniach wypisuje błędne liczby w niższych wierszach.
Ponowne używanie tej samej tablicy dla każdego wiersza. Jeśli za każdym razem dołączysz tę samą tablicę, a następnie ją zmienisz, każdy wiersz w odpowiedzi będzie taki jak ostatni.

Najczęstsze pytania4

Jaka jest złożoność czasowa generowania trójkąta Pascala?

Budowanie każdego wiersza na podstawie wiersza powyżej zajmuje O(n²) czasu dla n wierszy, ponieważ trójkąt zawiera około n²/2 elementów, a każdy z nich powstaje w wyniku jednego dodawania. Jest to optymalne, ponieważ musisz zapisać każdy element wyniku. Poza miejscem zajmowanym przez wynik algorytm wykorzystuje O(1) dodatkowej pamięci.

Jaki związek ma trójkąt Pascala ze współczynnikami dwumianowymi?

Wpis k w wierszu r, licząc oba od 0, to współczynnik dwumianowy C(r, k), czyli liczba sposobów wybrania k elementów spośród r. Zasada, że każdy wpis jest sumą dwóch wpisów nad nim, to tożsamość C(r, k) = C(r-1, k-1) + C(r-1, k). Dlatego też suma elementów w wierszu r wynosi 2^r.

Czy potrafisz obliczyć jeden wiersz bez budowania wierszy powyżej?

Tak. Zacznij od 1 i obliczaj każdy kolejny element na podstawie poprzedniego: C(r, k) = C(r, k-1) × (r-k+1) / k. Mnoż najpierw, a dopiero potem dziel, aby wynik dzielenia był dokładny, i użyj 64-bitowej liczby całkowitej do iloczynu. Wiersz r wymaga wtedy czasu O(r) i nie wymaga obliczania żadnych innych wierszy.

Dlaczego trójkąt Pascala jest problemem programowania dynamicznego?

Każdy wpis zależy od dwóch mniejszych podproblemów, czyli wpisów znajdujących się nad nim, a te podproblemy w dużej mierze się pokrywają: zwykła rekurencja oblicza je wciąż od nowa. Budowanie wierszy po kolei zapisuje każdy podproblem tylko raz i wykorzystuje go ponownie, co zmienia wykładniczą liczbę operacji w O(n²).

Python

def generate(numRows):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

numRows = 5

Oczekiwane

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]