Jalur Unik dan Jumlah Jalur Minimum pada Grid
Isi tabel DP 2D untuk jalur unik dengan dan tanpa rintangan, lalu sesuaikan untuk meminimalkan jumlah nilai di sepanjang jalur.
Jalur Unik dan Jumlah Jalur Minimum pada Grid adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Jalur Unik pada Kisi
Jalur Unik (LeetCode 62) menanyakan: dalam kisi berukuran m×n, ada berapa jalur berbeda dari sudut kiri atas ke sudut kanan bawah jika Anda hanya dapat bergerak ke kanan atau ke bawah? Untuk kisi berukuran 3×7, jawabannya adalah 28. Gagasan utamanya adalah bahwa setiap jalur menuju sel (i,j) pasti berasal dari (i-1,j) (atas) atau (i,j-1) (kiri), sehingga terbentuk formulasi DP 2D yang alami.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 2Tabel DP 2D untuk Jalur Unik
Definisikan dp[i][j] = jumlah jalur menuju sel (i,j). Baris pertama dan kolom pertama semuanya bernilai 1 (hanya ada satu cara untuk mencapai setiap sel pada baris teratas atau kolom paling kiri). Untuk sel lainnya: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Isi tabel baris demi baris, dan jawabannya adalah dp[m-1][n-1]. Kompleksitas waktu: O(m×n), ruang: O(m×n), yang dapat dikurangi menjadi O(n).
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)Optimisasi Ruang menjadi O(n)
Karena dp[i][j] hanya bergantung pada baris saat ini dan baris sebelumnya, Anda dapat mengganti tabel 2D lengkap dengan satu larik 1D. Inisialisasikan semua nilai ke 1, lalu untuk setiap baris, perbarui nilainya langsung: dp[j] += dp[j-1]. Setelah memproses baris i, dp[j] menyimpan nilai yang sebelumnya merupakan dp[i][j] dalam tabel 2D. Ini merupakan pola optimisasi umum untuk masalah DP 2D.
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28Jalur Unik II: Rintangan
Jalur Unik II (LeetCode 63) menambahkan rintangan (sel yang ditandai dengan 1) ke dalam kisi. Jalur apa pun yang melewati rintangan tidak valid, sehingga dp[i][j] = 0 jika obstacle[i][j] == 1. Selain itu, relasi rekurensinya tetap sama: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Jika titik awal atau akhir terhalang, hasilnya langsung 0. Inisialisasikan kasus dasar dengan cermat — setelah angka 1 muncul pada baris pertama atau kolom pertama, semua sel berikutnya pada baris atau kolom tersebut bernilai 0.
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2Masalah Jumlah Jalur Minimum
Jumlah Jalur Minimum (LeetCode 64) menanyakan: diberikan kisi berukuran m×n yang berisi bilangan non-negatif, temukan jalur dari kiri atas ke kanan bawah yang meminimalkan jumlah semua bilangan di sepanjang jalur (hanya bergerak ke kanan atau ke bawah). Sebagai contoh, pada [[1,3,1],[1,5,1],[4,2,1]], jalur 1→3→1→1→1 menghasilkan jumlah 7. Keadaan DP-nya sama seperti pada Jalur Unik, tetapi relasi rekurensinya kini menggunakan nilai minimum, bukan penjumlahan.
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)Implementasi DP untuk Jumlah Jalur Minimum
Definisikan dp[i][j] = biaya minimum untuk mencapai sel (i,j). Kasus dasar: dp[0][0] = grid[0][0]. Baris pertama: dp[0][j] = dp[0][j-1] + grid[0][j] (satu-satunya cara adalah datang dari kiri). Kolom pertama: dp[i][0] = dp[i-1][0] + grid[i][0] (satu-satunya cara adalah datang dari atas). Kasus umum: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Ini merupakan penerapan langsung prinsip optimalitas.
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7Jumlah Jalur Minimum di Tempat
Jika Anda diperbolehkan mengubah kisi masukan, Anda dapat memperbaruinya di tempat untuk menghindari alokasi tabel DP terpisah. Ini mengurangi ruang tambahan menjadi O(1) (di luar masukan). Pewawancara terkadang menanyakan optimisasi ini — pastikan apakah perubahan pada masukan diperbolehkan sebelum melakukannya. Jika tidak, trik larik bergulir 1D memberikan ruang O(n) tanpa mengubah masukan.
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Jumlah Jalur Minimum pada Segitiga
Segitiga (LeetCode 120) menanyakan jumlah jalur minimum dari atas ke bawah dalam larik segitiga, dengan setiap langkah menuju bilangan yang bersebelahan pada baris di bawahnya. DP dari bawah ke atas merupakan pendekatan yang paling sederhana: mulai dari baris kedua dari terakhir, lalu untuk setiap sel, tambahkan nilai minimum dari dua sel yang tepat berada di bawahnya. Cara ini menghindari pelacakan indeks awal dan secara alami mengalirkan jawaban ke puncak.
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)DP Kisi pada Ruang Bawah Tanah
Permainan Ruang Bawah Tanah (LeetCode 174) menanyakan kesehatan awal minimum yang diperlukan untuk menyelamatkan seorang putri di sudut kanan bawah kisi yang berisi sel negatif (kerusakan) dan positif (pemulihan). Anda harus bergerak ke kanan atau ke bawah. Triknya adalah mengisi tabel DP secara mundur (dari kanan bawah ke kiri atas), dengan menghitung kesehatan minimum yang diperlukan pada setiap sel. Pada setiap sel: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Kesehatan harus selalu setidaknya 1.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7Membandingkan Masalah DP Kisi
Masalah DP kisi memiliki struktur yang sama, tetapi berbeda dalam arah pengisian dan operasi transisi: Jalur Unik menggunakan penjumlahan (menghitung semua cara). Jumlah Jalur Minimum menggunakan nilai minimum (melakukan optimisasi). Permainan Ruang Bawah Tanah diisi secara mundur (kesehatan yang diperlukan dari masa mendatang). Saat menghadapi DP kisi yang baru, tanyakan kepada diri Anda: (1) Apa yang direpresentasikan oleh setiap sel? (2) Ke arah mana saya mengisi tabel? (3) Operasi apa yang menggabungkan sel-sel tetangga? Menjawab ketiga pertanyaan ini akan mengungkapkan keseluruhan solusi.
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')Rangkuman Kompleksitas DP Kisi
Semua masalah DP kisi di sini berjalan dalam waktu O(m×n). Ruang berkisar dari O(m×n) untuk tabel lengkap hingga O(n) dengan larik bergulir 1D, serta O(1) ruang tambahan ketika kisi dapat diubah langsung. Dalam wawancara, sebutkan optimisasi ruang O(n) setelah menyajikan solusi O(m×n) — ini menunjukkan pemahaman terhadap kompromi. Untuk semua masalah, pertimbangkan juga apakah terdapat pendekatan serakah yang lebih singkat (seperti rumus matematika untuk Jalur Unik).
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: Jalur Unik mengisi tabel 2D dengan dp[i][j] = dp[i-1][j] + dp[i][j-1] dan dapat dihitung dalam O(1) menggunakan kombinatorika, Jumlah Jalur Minimum menggunakan struktur yang sama tetapi mengganti penjumlahan dengan min untuk memperoleh biaya jalur optimal, dan semua masalah DP kisi memiliki pola berupa pendefinisian keadaan untuk setiap sel dan pemilihan operator transisi (sum, min, max). Selanjutnya, kita akan mempelajari Subsekuens Bersama Terpanjang menggunakan DP 2D pada dua untaian.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Jalur Unik dan Jumlah Jalur Minimum pada Grid” gratis?
Ya — teks lengkap “Jalur Unik dan Jumlah Jalur Minimum pada Grid” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Jalur Unik dan Jumlah Jalur Minimum pada Grid”?
Isi tabel DP 2D untuk jalur unik dengan dan tanpa rintangan, lalu sesuaikan untuk meminimalkan jumlah nilai di sepanjang jalur. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Jalur Unik dan Jumlah Jalur Minimum pada Grid” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Jalur Unik dan Jumlah Jalur Minimum pada Grid
- Longest Common Subsequence
- Jarak Edit (Levenshtein)
- Optimasi Ruang untuk DP 2D