Jumlah Jalur Minimum dengan Rintangan

Sekarang setiap sel menyimpan sebuah nilai dan Anda menginginkan rute termurah menuju sudut. Tujuannya bergeser dari menghitung jalur menjadi meminimalkan biaya.

Misalkan dp[i][j] adalah biaya total terkecil untuk mencapai sel (i, j). Kisanya sama, gerakannya sama, tetapi kini kita melacak jumlah, bukan banyaknya jalur.

Anda memilih tetangga masuk yang lebih murah, lalu menambahkan nilai sel saat ini. Pilihan minimum tersebut merupakan inti dari relasi rekurensi.

Rintangan adalah sel yang tidak dapat Anda tempati. Berikan biaya tak terhingga agar jalur yang melewatinya tidak pernah menjadi jalur minimum.

Ketika kisi menandai sebuah sel sebagai terblokir, cukup atur dp-nya menjadi tak terhingga dan lanjutkan. Langkah minimum akan menghindarinya secara alami.

Jika sel awal itu sendiri terblokir, tidak ada jalur sama sekali. Periksa hal tersebut terlebih dahulu agar Anda tidak mengembalikan biaya yang tidak bermakna.

Titik awal tidak memiliki tetangga asal, sehingga biayanya hanya nilainya sendiri. Atur dp[0][0] sebelum perulangan dijalankan.

Baris teratas hanya mengalir dari kiri dan kolom paling kiri hanya dari atas. Tangani batas ini agar Anda tidak membaca di luar kisi.

Menambahkan sesuatu ke tak terhingga tetap menghasilkan tak terhingga, sehingga sel yang sepenuhnya terhalang mempertahankan biaya INF. Sel yang tidak dapat dicapai menunjukkan keadaannya secara otomatis.

Biaya minimum berada di sel kanan bawah. Jika nilainya masih tak terhingga, tidak ada jalur yang valid sama sekali.

Selalu melangkah menuju tetangga yang lebih kecil dapat menjebak Anda. Hanya DP lengkap yang menjamin jalur termurah secara global, bukan sekadar melihat pilihan secara serakah.

Bagaimana cara membuat DP jalur menghindari sel yang terblokir tanpa menangani setiap tetangga secara khusus?

Ambil tetangga yang lebih murah, tambahkan nilai sel, atur sel yang terblokir menjadi tak terhingga, lalu baca sudutnya. INF di sana berarti tidak ada jalur. 🧱