Tentukan Keadaan dan Peralihan

Setiap DP bermula dengan menamakan satu keadaan: apakah sebenarnya yang diwakili oleh dp[i]? Pastikan ayat ini tepat dan langkah seterusnya akan menjadi lebih mudah.

Tulis maksudnya dengan kata-kata: dp[i] = jawapan bagi i item pertama. Takrif keadaan yang kabur membawa kepada rekurens yang bermasalah.

Peralihan menerangkan cara dp[i] dibina daripada keadaan terdahulu. Inilah persamaan rekurens yang menjadi teras penyelesaian Anda.

Kes asas ialah keadaan terkecil yang boleh Anda ketahui secara langsung. Tanpa titik asas yang betul, setiap nilai seterusnya akan tersasar.

Setiap keadaan mesti diisi selepas keadaan yang menjadi kebergantungannya. Peraturan kebergantungan itu menentukan arah gelung Anda.

Tentukan sel yang menyimpan hasil akhir. Selalunya sel itu ialah dp[n], tetapi kadangkala hasilnya ialah nilai maksimum di seluruh jadual.

Bilangan keadaan berbeza menentukan bajet masa Anda. DP satu dimensi bagi n item mempunyai O(n) keadaan untuk diisi.

Jumlah masa ialah bilangan keadaan didarab dengan kerja bagi setiap peralihan. Peralihan O(n) dalam n keadaan memberikan O(n kuasa dua).

Jika satu indeks tidak dapat mewakili keadaan, tambahkan indeks lain. Dimensi kedua menukarkan dp[i] kepada dp[i][j].

Untuk mendapatkan semula penyelesaian sebenar, simpan peralihan yang menang pada setiap keadaan, kemudian telusuri ke belakang bermula daripada jawapan.

Keadaan, peralihan, kes asas, susunan, jawapan. Tetapkan kelima-lima perkara ini dan hampir semua hubungan rekurens DP akan terbentuk dengan sendirinya.

Anda kini boleh mentakrifkan keadaan, menulis peralihannya, menetapkan kes asas dan menentukan lokasi jawapan. Pelan ini menukar DP daripada kaedah cuba jaya kepada resipi yang tersusun.