Unique Paths

SedangDynamic programming Matematika dan simulasi

+10

Sebuah robot mulai dari sel kiri atas pada grid dengan m baris dan n kolom, lalu harus mencapai sel kanan bawah. Setiap gerakan membawanya satu sel ke kanan atau satu sel ke bawah. Kembalikan jumlah jalur berbeda yang dapat ditempuhnya.

Fungsi

uniquePaths(m: integer, n: integer) → integer

minteger: jumlah baris dalam grid
ninteger: jumlah kolom dalam kisi
Mengembalikaninteger: jumlah jalur berbeda dari sel kiri atas ke sel kanan bawah

Batasan

1 ≤ m, n ≤ 100
Jawabannya paling besar 2 × 10⁹, jadi nilainya muat dalam bilangan bulat bertanda 32-bit.

Contoh

Input: m = 3n = 4
Output: 10
Penjelasan: Setiap jalur memiliki 2 langkah ke bawah dan 3 langkah ke kanan, total 5 langkah. Sebuah jalur ditentukan oleh 2 dari 5 langkah yang bergerak ke bawah, dan ada 10 cara untuk memilihnya.

Pertanyaan lanjutan

Untuk grid 100 × 100, jawabannya memiliki 59 digit. Bagaimana kamu mengembalikannya dalam modulo 10^9+7 dengan rumus tersebut, saat membaginya dengan i tidak lagi berfungsi?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Mencantumkan jalurnya sia-sia: kisi berukuran 17 × 17 memiliki 601,080,390 jalur. Hitung saja. Jalur menuju sebuah sel adalah jalur menuju sel di atasnya ditambah jalur menuju sel di sebelah kirinya, sehingga tabel dapat diisi dalam satu kali lintasan. Dan sebuah jalur hanyalah urutan gerakan ke bawah dan ke kanan, yang menghasilkan rumus tertutup.

Hitung setiap jalur dengan rekursi

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Gerakan terakhir robot berasal dari sel di atas dengan bergerak ke bawah atau dari sel di sebelah kiri dengan bergerak ke kanan. Jadi uniquePaths(m, n) = uniquePaths(m-1, n) + uniquePaths(m, n-1), dan grid dengan satu baris atau satu kolom memiliki tepat 1 jalur. Setiap jalur berakhir dengan tepat satu dari dua gerakan tersebut, jadi setiap jalur dihitung sekali.

Setiap jalur berakhir pada kasus dasar yang mengembalikan 1, jadi jumlah pemanggilan setidaknya sama dengan jawabannya: grid berukuran 17 × 17 memerlukan lebih dari 600 juta pemanggilan. Grid-grid kecil yang sama dihitung berulang kali.

Algoritma

Jika m atau n bernilai 1, kembalikan 1: satu-satunya jalur berupa garis lurus.
Jika tidak, hitung jalur yang langkah terakhirnya ke bawah, uniquePaths(m-1, n).
Hitung jalur yang langkah terakhirnya ke kanan, uniquePaths(m, n-1).
Kembalikan jumlahnya.

def uniquePaths(m, n):
    # One row or one column: the only path is a straight line
    if m == 1 or n == 1:
        return 1
    # The last move came down from the row above or right from the column before
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

Isi kisi satu baris setiap kali

Intuisi

Rekursi terus menanyakan sel m × n yang sama. Hitung setiap sel sekali, dengan urutan yang memastikan nilai masukannya sudah siap.

State: paths[r][c] adalah jumlah jalur dari sel kiri atas ke baris r, kolom c. Relasi rekurensi: paths[r][c] = paths[r-1][c] + paths[r][c-1], jalur yang datang dari atas ditambah jalur yang datang dari kiri. Kasus dasar: setiap sel di baris teratas dan kolom paling kiri memiliki 1 jalur. Urutan: baris demi baris, dari kiri ke kanan. Untuk m = 3, n = 4, baris-barisnya adalah 1 1 1 1, 1 2 3 4, 1 3 6 10, dan jawabannya 10.

Pengisian hanya membaca baris di atas, jadi cukup gunakan satu baris. Sebelum kamu memperbarui row[c], nilainya masih menyimpan jumlah dari atas, sedangkan row[c-1] sudah menyimpan jumlah baru di sebelah kirinya. Jadi, row[c] += row[c-1] sudah mencakup seluruh relasi rekurensi dengan memori O(n).

Algoritma

Buat row dengan n entri, semuanya 1: baris teratas.
Ulangi m-1 kali, sekali untuk setiap baris di bawah baris teratas.
Di setiap baris, untuk c dari 1 hingga n-1, tambahkan row[c-1] ke row[c]. row[0] tetap 1: itulah kolom paling kiri.
Kembalikan row[n-1].

def uniquePaths(m, n):
    # row[c] counts the paths into column c of the current row.
    # The top row is all 1s: the only way along it is straight right.
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            # Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
            row[c] += row[c - 1]
    return row[n - 1]

Hitung langkah dengan koefisien binomial

Intuisi

Setiap jalur menempuh m-1 langkah ke bawah dan n-1 langkah ke kanan, dengan total m+n-2 langkah dalam urutan tertentu. Setiap urutan adalah jalur yang valid: jalur itu tidak pernah menempuh lebih dari m-1 langkah ke bawah atau n-1 langkah ke kanan, sehingga tidak pernah keluar dari kisi. Jadi, jalur ditentukan dengan memilih langkah mana dari m-1 langkah yang menuju ke bawah, dan jawabannya adalah C(m+n-2, m-1).

Bangun koefisien tanpa faktorial. Dengan N = m+n-2 dan k = min(m, n)-1, kalikan dengan N-k+i, lalu bagi dengan i, untuk i dari 1 hingga k. Setelah langkah i, nilainya adalah C(N-k+i, i), sebuah bilangan bulat, jadi setiap pembagian menghasilkan nilai yang tepat. Untuk m = 3, n = 4: 1 × 4 / 1 = 4, lalu 4 × 5 / 2 = 10. Memilih sisi yang lebih pendek menjaga perulangan tetap pada 99 langkah atau kurang.

Algoritma

Tetapkan N = m+n-2, jumlah langkah, dan k = min(m, n)-1.
Mulai hitungan 64-bit dengan nilai 1.
Untuk i dari 1 hingga k, kalikan hitungan dengan N-k+i, lalu bagi dengan i.
Kembalikan hitungan.

def uniquePaths(m, n):
    # A path is m+n-2 moves; count the ways to choose which of them go down.
    # Choose along the shorter side so the loop stays short.
    moves = m + n - 2
    k = min(m, n) - 1
    count = 1
    for i in range(1, k + 1):
        # count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
        count = count * (moves - k + i) // i
    return count

Jebakan dan kasus tepi

Menghitung (m+n-2)! lalu membaginya dengan dua faktorial lainnya. 21! sudah melampaui rentang 64-bit, dan m+n-2 mencapai 105 pada grid 100 × 7.
Melakukan pembagian sebelum perkalian, seperti pada count / i * (N-k+i). count tidak selalu merupakan kelipatan i, jadi hasil pembagian dipotong.
Menyimpan hasil perkalian berjalan dalam 32 bit. Sebelum pembagian terakhir, nilainya adalah k dikali jawabannya: 16 × 601,080,390, sekitar 9.6 × 10^9, untuk grid 17 × 17.
Memulai baris paling atas atau kolom paling kiri dari 0, bukan 1. Setiap sel menjadi 0, meskipun grid dengan satu baris atau satu kolom memiliki tepat 1 jalur.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Unique Paths?

Tabel pemrograman dinamis membutuhkan waktu O(m × n) dan ruang O(n) jika kamu menyimpan satu baris. Rumus binomial membutuhkan waktu O(min(m, n)) dan ruang O(1). Rekursi biasa melakukan setidaknya sebanyak jumlah jalur pemanggilan, yang bersifat eksponensial terhadap m + n.

Bagaimana cara menyelesaikan Unique Paths saat beberapa sel terhalang?

Gunakan tabel yang sama, lalu tetapkan jumlah jalur pada sel yang terhalang menjadi 0 agar tidak ada jalur yang melewatinya. Baris teratas dan kolom paling kiri tidak lagi semuanya bernilai 1: setiap sel setelah sel yang terhalang di baris teratas memiliki 0 jalur. Rumusnya tidak lagi berfungsi karena rumus tersebut mengasumsikan bahwa semua urutan gerakan diperbolehkan.

Mengapa tabel Jalur Unik cocok dengan segitiga Pascal?

Setiap sel menjumlahkan sel di atasnya dan sel di sebelah kirinya. Aturan ini membentuk segitiga Pascal jika dibaca sepanjang diagonalnya. Sel pada baris r dan kolom c berisi C(r+c, r), jadi sel kanan bawah berisi C(m+n-2, m-1), sesuai rumus binomial.

def uniquePaths(m, n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

m = 3
n = 4

Output yang diharapkan

Unique Paths

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Hitung setiap jalur dengan rekursi

Isi kisi satu baris setiap kali

Hitung langkah dengan koefisien binomial

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa