Pascal's Triangle

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

O(n²) dla n wierszy: trójkąt ma około n²/2 elementów i każdy wymaga jednego dodawania. To rozwiązanie jest optymalne, ponieważ musisz zapisać każdy element wyniku. Dodatkowa przestrzeń poza wynikiem to O(1) .

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

Element k wiersza r , licząc od 0, to C(r, k) , czyli liczba sposobów wyboru k elementów spośród r . Reguła sumowania to tożsamość C(r, k) = C(r-1, k-1) + C(r-1, k) , a suma elementów w wierszu r wynosi 2^r , czyli liczbę podzbiorów zbioru r elementów.

Q: Czy potrafisz obliczyć jeden wiersz bez budowania wierszy nad nim?

Tak. Zacznij od 1 i obliczaj każdy kolejny element na podstawie poprzedniego: C(r, k) = C(r, k-1) × (r-k+1) / k . Najpierw mnoż, a dopiero potem dziel, aby wynik dzielenia był dokładny, i użyj 64-bitowej liczby całkowitej dla iloczynu. Wiersz r zajmuje wtedy O(r) czasu.

Ł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 element pomiędzy nimi jest sumą dwóch elementów znajdujących się bezpośrednio nad nim. Otrzymujesz liczbę całkowitą numRows. Zwróć pierwsze numRows wierszy trójkąta, zaczynając od górnego, każdy wiersz jako tablicę liczb całkowitych.

Funkcja

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

numRowsinteger: ile wierszy trójkąta zbudować
Zwracainteger-2d-array: pierwszych numRows wierszy, najpierw górny wiersz

Ograniczenia

1 ≤ numRows ≤ 30
Każda wartość z pierwszych 30 wierszy mieści się w 32-bitowej liczbie całkowitej ze znakiem. Największa to 77558760 i znajduje się w środku 30. wiersza.

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 wewnętrzny wpis dodaje dwie liczby znajdujące się nad nim. Czwarty wiersz: 3 = 1 + 2 i 3 = 2 + 1. Piąty wiersz: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

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

Pytanie dodatkowe

Czy możesz zachować tylko jedną tablicę i aktualizować ją na miejscu, wiersz po wierszu? 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

Każdy element jest sumą dwóch elementów z wiersza powyżej. Ponowne obliczanie tej reguły od początku dla każdego elementu wyznacza te same wartości, a nakład pracy podwaja się z każdym wierszem. Zwracane wiersze zawierają zapisane odpowiedzi na te mniejsze problemy, więc buduj trójkąt od góry do dołu, każdy wiersz na podstawie poprzedniego.

Oblicz rekurencyjnie każdy wpis

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

Intuicja

Numeruj wiersze i pozycje od 0. Definicja staje się funkcją: entry(row, col) ma wartość 1 na krawędziach, gdzie col wynosi 0 lub row, a w przeciwnym razie entry(row-1, col-1) + entry(row-1, col). Jest poprawna, ponieważ taka jest definicja.

Rekurencja kończy się tylko na krawędziach, które zwracają 1, więc obliczenie wpisu o wartości v wymaga około 2v wywołań. Suma elementów wiersza r wynosi do 2^r, więc dla 30 wierszy potrzeba około 2^31 wywołań, czyli ponad dwóch miliardów.

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

Zbuduj każdy wiersz na podstawie wiersza powyżej

Intuicja

Rekurencja wciąż prosi o wartości z wcześniejszych wierszy, a i tak je tworzysz. Obliczaj więc wiersze od góry do dołu i podczas wypełniania wiersza r odczytuj wiersz r-1, który jest już gotowy. Każda wartość wymaga jednego dodawania: tabela mniejszych wyników jest samym wynikiem.

Rozpoczęcie każdego wiersza od r + 1 jedynek wyznacza obie krawędzie, więc wiersze 0 i 1, które nie mają pozycji wewnętrznych, nie wymagają obsługi specjalnego przypadku. Trójkąt zawiera 1 + 2 + ... + n, czyli około n²/2, wartości, więc praca wymaga O(n²) czasu i nie potrzebuje pamięci poza wynikiem: 465 wartości dla 30 wierszy 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żdego col od 1 do row-1 ustaw jego wartość na sumę elementów z pozycji 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

Zwracanie numRows + 1 wierszy. Numerowanie zaczyna się od 0, więc ostatni potrzebny wiersz to numRows-1.
Uruchamianie pętli wewnętrznej dla krawędzi. Pozycja 0 nie ma lewego elementu nadrzędnego, a pozycja row nie ma prawego, więc odczytanie ich powoduje wyjście poza zakres.
Zakres, który zawodzi dla małych wierszy. 1..<row w Swift powoduje awarię, gdy row wynosi 0, a 2:(row-1) w R odlicza w dół do 1, gdy row wynosi 2.
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.
Dołączanie tej samej tablicy dla każdego wiersza, a następnie jej modyfikowanie. Każdy wiersz w wyniku staje się ostatnim wierszem.

Najczęstsze pytania3

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

O(n²) dla n wierszy: trójkąt ma około n²/2 elementów i każdy wymaga jednego dodawania. To rozwiązanie jest optymalne, ponieważ musisz zapisać każdy element wyniku. Dodatkowa przestrzeń poza wynikiem to O(1).

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

Element k wiersza r, licząc od 0, to C(r, k), czyli liczba sposobów wyboru k elementów spośród r. Reguła sumowania to tożsamość C(r, k) = C(r-1, k-1) + C(r-1, k), a suma elementów w wierszu r wynosi 2^r, czyli liczbę podzbiorów zbioru r elementów.

Czy potrafisz obliczyć jeden wiersz bez budowania wierszy nad nim?

Tak. Zacznij od 1 i obliczaj każdy kolejny element na podstawie poprzedniego: C(r, k) = C(r, k-1) × (r-k+1) / k. Najpierw mnoż, a dopiero potem dziel, aby wynik dzielenia był dokładny, i użyj 64-bitowej liczby całkowitej dla iloczynu. Wiersz r zajmuje wtedy O(r) czasu.

def generate(numRows):
    # Napisz kod tutaj

Test #1

Test #2

Argument

numRows = 5

Oczekiwany wynik

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