Apa itu pemrograman dinamis? [Tutup]

276

Apa itu pemrograman dinamis ?

Apa bedanya dengan rekursi, memoisasi, dll?

Saya telah membaca artikel wikipedia di dalamnya, tetapi saya masih belum benar-benar memahaminya.

smac89
sumber
1
Berikut adalah salah satu tutorial oleh Michael A. Trick dari CMU yang saya temukan sangat membantu: mat.gsia.cmu.edu/classes/dynamic/dynamic.html Hal ini tentunya sebagai tambahan untuk semua sumber daya yang direkomendasikan (semua sumber daya lainnya, khususnya CLR dan Kleinberg, Tardos sangat bagus!). Alasan mengapa saya menyukai tutorial ini adalah karena ia memperkenalkan konsep-konsep lanjutan secara bertahap. Ini adalah materi yang agak kuno tetapi merupakan tambahan yang bagus untuk daftar sumber daya yang disajikan di sini. Lihat juga halaman Steven Skiena dan ceramah tentang Pemrograman Dinamis: cs.sunysb.edu/~algorith/video-lectures http:
Edmon
11
Saya selalu menemukan "Pemrograman Dinamis" istilah yang membingungkan - "Dinamis" menunjukkan tidak-statis, tapi apa itu "Pemrograman Statis"? Dan "... Pemrograman" mengingatkan "Pemrograman Berorientasi Objek" dan "Pemrograman Fungsional", menyarankan DP adalah paradigma pemrograman. Saya tidak benar-benar memiliki nama yang lebih baik (mungkin "Algoritma Dinamis"?) Tapi sayang sekali kami terjebak dengan yang ini.
dimo414
3
@ dimo414 "Pemrograman" di sini lebih terkait dengan "pemrograman linier" yang termasuk dalam kelas metode optimasi matematis. Lihat artikel Optimalisasi matematika untuk daftar metode pemrograman matematika lainnya.
syockit
1
@ dimo414 "Pemrograman" dalam konteks ini mengacu pada metode tabular, bukan untuk menulis kode komputer. - Coreman
user2618142
Masalah minimisasi biaya tiket bus yang dijelaskan dalam cs.stackexchange.com/questions/59797/… paling baik diselesaikan dalam pemrograman dinamis.
truthadjustr

Jawaban:

210

Pemrograman dinamis adalah saat Anda menggunakan pengetahuan masa lalu untuk membuat penyelesaian masalah di masa depan lebih mudah.

Contoh yang baik adalah memecahkan urutan Fibonacci untuk n = 1.000,002.

Ini akan menjadi proses yang sangat panjang, tetapi bagaimana jika saya memberi Anda hasil untuk n = 1.000.000 dan n = 1.000.001? Tiba-tiba masalahnya menjadi lebih mudah dikelola.

Pemrograman dinamis banyak digunakan dalam masalah string, seperti masalah mengedit string. Anda memecahkan sebagian masalah dan kemudian menggunakan informasi itu untuk menyelesaikan masalah asli yang lebih sulit.

Dengan pemrograman dinamis, Anda menyimpan hasil Anda di semacam tabel secara umum. Ketika Anda membutuhkan jawaban untuk suatu masalah, Anda mereferensikan tabel dan melihat apakah Anda sudah tahu apa itu. Jika tidak, Anda menggunakan data di meja Anda untuk memberi diri Anda batu loncatan menuju jawabannya.

Buku Cormen Algorithms memiliki bab yang bagus tentang pemrograman dinamis. DAN gratis di Google Buku! Lihat di sini.

samoz
sumber
50
Bukankah Anda baru saja menggambarkan memoisasi?
dreadwail
31
Saya akan mengatakan memoisasi adalah bentuk pemrograman dinamis, ketika fungsi / metode memoized adalah yang rekursif.
Daniel Huckstep
6
Jawaban yang bagus, hanya akan menambahkan penyebutan tentang sub-struktur yang optimal (misalnya, setiap subset dari setiap lintasan di sepanjang lintasan terpendek dari A ke B itu sendiri adalah lintasan terpendek antara 2 titik akhir dengan asumsi metrik jarak yang mengamati ketimpangan segitiga).
Shea
5
Saya tidak akan mengatakan "lebih mudah", tetapi lebih cepat. Kesalahpahaman yang umum adalah bahwa dp memecahkan masalah yang tidak bisa dilakukan oleh algoritma naif dan bukan itu masalahnya. Bukan masalah fungsionalitas tetapi kinerja.
andandandand
6
Menggunakan memoisasi, masalah pemrograman dinamis dapat diselesaikan secara top down. yaitu memanggil fungsi untuk menghitung nilai akhir, dan fungsi itu pada gilirannya memanggilnya sendiri secara rekursif untuk menyelesaikan submasalah. Tanpanya, masalah pemrograman dinamis hanya bisa diselesaikan secara bottom up.
Pranav
175

Pemrograman dinamis adalah teknik yang digunakan untuk menghindari komputasi beberapa kali dari subproblem yang sama dalam algoritma rekursif.

Mari kita ambil contoh sederhana dari angka Fibonacci: menemukan angka Fibonacci ke- n yang ditentukan oleh

F n = F n-1 + F n-2 dan F 0 = 0, F 1 = 1

Pengulangan

Cara yang jelas untuk melakukan ini adalah rekursif:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Pemrograman Dinamis

  • Top Down - Memoization

Rekursi melakukan banyak perhitungan yang tidak perlu karena angka Fibonacci yang diberikan akan dihitung beberapa kali. Cara mudah untuk meningkatkan ini adalah dengan meng-cache hasil:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]
  • Bawah ke Atas

Cara yang lebih baik untuk melakukan ini adalah dengan menyingkirkan rekursi bersama-sama dengan mengevaluasi hasil dalam urutan yang benar:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

Kami bahkan dapat menggunakan ruang konstan dan hanya menyimpan hasil parsial yang diperlukan di sepanjang jalan:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi
  • Bagaimana menerapkan pemrograman dinamis?

    1. Temukan rekursi dalam masalah.
    2. Top-down: menyimpan jawaban untuk setiap sub-masalah dalam sebuah tabel untuk menghindari harus menghitung ulang mereka.
    3. Bawah ke atas: Temukan urutan yang tepat untuk mengevaluasi hasil sehingga hasil sebagian tersedia saat dibutuhkan.

Pemrograman dinamis umumnya bekerja untuk masalah yang memiliki urutan inheren dari kiri ke kanan seperti string, tree atau integer sequence. Jika algoritma rekursif naif tidak menghitung subproblem yang sama beberapa kali, pemrograman dinamis tidak akan membantu.

Saya membuat kumpulan masalah untuk membantu memahami logika: https://github.com/tristanguigue/dynamic-programing

Tristan
sumber
3
Ini adalah jawaban yang bagus dan pengumpulan masalah di Github juga sangat berguna. Terima kasih!
p4sh4
Hanya karena penasaran untuk mengklarifikasi hal - menurut Anda, implementasi rekursif menggunakan relasi berulang dan memoisasi adalah pemrograman dinamis?
Codor
Terima kasih untuk penjelasannya. Apakah ada kondisi yang hilang dari bawah ke atas: if n in cacheseperti contoh dari atas ke bawah atau saya kehilangan sesuatu.
DavidC
Apakah saya mengerti dengan benar bahwa setiap loop di mana nilai yang dihitung pada setiap iterasi digunakan dalam iterasi selanjutnya adalah contoh pemrograman dinamis?
Alexey
Bisakah Anda memberikan referensi untuk interpretasi yang Anda berikan, termasuk kasus khusus top-down dan bottom-up?
Alexey
37

Memoisasi adalah ketika Anda menyimpan hasil sebelumnya dari panggilan fungsi (fungsi nyata selalu mengembalikan hal yang sama, diberi input yang sama). Itu tidak membuat perbedaan untuk kompleksitas algoritmik sebelum hasilnya disimpan.

Rekursi adalah metode pemanggilan fungsi itu sendiri, biasanya dengan dataset yang lebih kecil. Karena sebagian besar fungsi rekursif dapat dikonversi ke fungsi iteratif yang serupa, ini tidak membuat perbedaan untuk kompleksitas algoritme.

Pemrograman dinamis adalah proses pemecahan sub-masalah yang lebih mudah untuk diselesaikan dan membangun jawabannya. Sebagian besar algoritma DP akan berjalan antara algoritma Greedy (jika ada) dan algoritma eksponensial (sebutkan semua kemungkinan dan temukan yang terbaik).

  • Algoritma DP dapat diimplementasikan dengan rekursi, tetapi tidak harus demikian.
  • Algoritma DP tidak dapat dipercepat dengan memoisasi, karena setiap sub-masalah hanya pernah diselesaikan (atau fungsi "selesaikan" disebut) sekali.
philomathohollic
sumber
Sangat jelas. Saya berharap instruktur algoritma dapat menjelaskan ini dengan baik.
Kelly S. French
21

Ini merupakan pengoptimalan dari algoritme Anda yang memotong waktu berjalan.

Sementara Greedy Algorithm biasanya disebut naif , karena dapat berjalan beberapa kali pada set data yang sama, Dynamic Programming menghindari jebakan ini melalui pemahaman yang lebih dalam tentang hasil parsial yang harus disimpan untuk membantu membangun solusi akhir.

Contoh sederhana adalah melintasi pohon atau grafik hanya melalui node yang akan berkontribusi dengan solusi, atau menempatkan ke dalam tabel solusi yang telah Anda temukan sejauh ini sehingga Anda dapat menghindari melintasi node yang sama berulang-ulang.

Berikut adalah contoh masalah yang cocok untuk pemrograman dinamis, dari juri online UVA: Edit Steps Ladder.

Saya akan membuat pengarahan singkat tentang bagian penting dari analisis masalah ini, diambil dari buku Programming Challenges, saya sarankan Anda memeriksanya.

Perhatikan baik-baik masalah itu, jika kita mendefinisikan fungsi biaya yang memberi tahu kita sejauh mana hubungan dua string, kita harus mempertimbangkan dua jenis perubahan alami:

Substitusi - ubah satu karakter dari pola "s" ke karakter berbeda di teks "t", seperti mengubah "shot" menjadi "spot".

Sisipan - masukkan satu karakter ke dalam pola "s" untuk membantunya mencocokkan teks "t", seperti mengubah "lalu" menjadi "agog".

Penghapusan - hapus satu karakter dari pola "s" untuk membantunya mencocokkan teks "t", seperti mengubah "jam" menjadi "kami".

Ketika kami menetapkan masing-masing operasi ini dengan biaya satu langkah, kami menentukan jarak edit antara dua string. Jadi bagaimana kita menghitungnya?

Kita dapat mendefinisikan algoritma rekursif menggunakan pengamatan bahwa karakter terakhir dalam string harus dicocokkan, diganti, dimasukkan atau dihapus. Memotong karakter dalam operasi edit terakhir membuat operasi pasangan menyisakan sepasang string yang lebih kecil. Biarkan i dan j masing-masing menjadi karakter terakhir dari awalan dan t yang relevan. ada tiga pasang string yang lebih pendek setelah operasi terakhir, sesuai dengan string setelah pertandingan / substitusi, penyisipan atau penghapusan. Jika kami tahu biaya mengedit tiga pasang string yang lebih kecil, kami dapat memutuskan opsi mana yang mengarah ke solusi terbaik dan memilih opsi yang sesuai. Kita dapat mempelajari biaya ini, melalui hal menakjubkan yang merupakan rekursi:

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

Algoritma ini benar, tetapi juga sangat lambat.

Berjalan di komputer kita, perlu beberapa detik untuk membandingkan dua string 11-karakter, dan perhitungannya menghilang menjadi tidak pernah mendarat pada sesuatu yang lebih lama.

Mengapa algoritma ini sangat lambat? Dibutuhkan waktu yang eksponensial karena menghitung ulang nilai berulang kali. Pada setiap posisi dalam string, rekursi bercabang tiga cara, yang berarti ia tumbuh pada tingkat setidaknya 3 ^ - memang, bahkan lebih cepat karena sebagian besar panggilan mengurangi hanya satu dari dua indeks, bukan keduanya.

Jadi bagaimana kita bisa membuat algoritma ini praktis? Pengamatan penting adalah bahwa sebagian besar panggilan rekursif ini menghitung hal-hal yang telah dihitung sebelumnya. Bagaimana kami bisa tahu? Yah, hanya ada | s | · | T | kemungkinan panggilan rekursif unik, karena hanya ada banyak pasangan berbeda (i, j) yang berfungsi sebagai parameter panggilan rekursif.

Dengan menyimpan nilai untuk masing-masing pasangan (i, j) ini dalam sebuah tabel, kita dapat menghindari penghitungan ulang dan hanya mencarinya sesuai kebutuhan.

Tabel adalah matriks dua dimensi m di mana masing-masing | s | · | t | sel berisi biaya solusi optimal subproblem ini, serta pointer orangtua yang menjelaskan bagaimana kami sampai ke lokasi ini:

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

Versi pemrograman dinamis memiliki tiga perbedaan dari versi rekursif.

Pertama, ini mendapatkan nilai menengah menggunakan pencarian tabel alih-alih panggilan rekursif.

** Kedua, ** pembaruan bidang induk dari setiap sel, yang akan memungkinkan kita untuk merekonstruksi urutan edit nanti.

** Ketiga, ** Ketiga, ini diinstrumentasi menggunakan cell()fungsi tujuan yang lebih umum daripada hanya mengembalikan m [| s |] [| t |] .cost. Ini akan memungkinkan kita untuk menerapkan rutinitas ini ke kelas masalah yang lebih luas.

Di sini, analisis yang sangat khusus tentang apa yang diperlukan untuk mengumpulkan hasil parsial paling optimal, adalah apa yang membuat solusi itu "dinamis".

Inilah alternatif, solusi lengkap untuk masalah yang sama. Ini juga "dinamis" walaupun eksekusinya berbeda. Saya sarankan Anda memeriksa seberapa efisien solusinya dengan mengirimkannya ke juri online UVA. Saya merasa luar biasa bagaimana masalah yang sedemikian berat ditangani dengan sangat efisien.

andandandand
sumber
Apakah penyimpanan benar-benar diperlukan untuk pemrograman yang dinamis? Bukankah jumlah pekerjaan yang dilewati memenuhi syarat suatu algoritma sebagai dinamis?
Nthalk
Anda harus mengumpulkan hasil langkah demi langkah yang optimal untuk membuat algoritma "dinamis". Pemrograman Dinamis berasal dari karya Bellman di OR, jika Anda mengatakan "bahwa melompati jumlah kata adalah pemrograman dinamis" Anda mendevaluasi istilah tersebut, karena heuristik pencarian apa pun adalah pemrograman dinamis. en.wikipedia.org/wiki/Dynamic_programming
andandandand
12

Bit kunci dari pemrograman dinamis adalah "sub-masalah yang tumpang tindih" dan "substruktur optimal". Sifat-sifat masalah ini berarti bahwa solusi optimal terdiri dari solusi optimal untuk sub-masalahnya. Misalnya, masalah jalur terpendek menunjukkan substruktur optimal. Jalur terpendek dari A ke C adalah jalur terpendek dari A ke beberapa simpul B diikuti oleh jalur terpendek dari simpul B ke C.

Secara lebih rinci, untuk memecahkan masalah jalur terpendek Anda akan:

  • temukan jarak dari titik awal ke setiap titik yang menyentuhnya (katakanlah dari A ke B dan C)
  • temukan jarak dari simpul tersebut ke simpul yang menyentuhnya (dari B ke D dan E, dan dari C ke E dan F)
  • kita sekarang tahu jalur terpendek dari A ke E: itu adalah jumlah terpendek dari Ax dan xE untuk beberapa simpul x yang telah kita kunjungi (baik B atau C)
  • ulangi proses ini sampai kita mencapai simpul tujuan akhir

Karena kami bekerja dari bawah ke atas, kami sudah memiliki solusi untuk sub-masalah ketika tiba saatnya untuk menggunakannya, dengan memoise mereka.

Ingat, masalah pemrograman dinamis harus memiliki sub-masalah yang tumpang tindih, dan substruktur yang optimal. Menghasilkan urutan Fibonacci bukanlah masalah pemrograman yang dinamis; menggunakan memoisasi karena memiliki sub-masalah yang tumpang tindih, tetapi tidak memiliki substruktur yang optimal (karena tidak ada masalah optimasi yang terlibat).

Nick Lewis
sumber
1
IMHO, ini adalah satu-satunya jawaban yang masuk akal dalam hal pemrograman dinamis. Saya ingin tahu karena ketika orang sudah mulai menjelaskan DP menggunakan angka Fibonacci (hampir tidak relevan).
Terry Li
@TerryLi, Ini mungkin masuk akal, tapi itu tidak mudah dimengerti. Masalah angka Fibonacci diketahui dan mudah dipahami.
Ajay
5

Pemrograman Dinamis

Definisi

Dynamic programming (DP) adalah teknik desain algoritma umum untuk menyelesaikan masalah dengan sub-masalah yang tumpang tindih. Teknik ini ditemukan oleh ahli matematika Amerika "Richard Bellman" pada 1950-an.

Ide Kunci

Gagasan utamanya adalah menyimpan jawaban yang tumpang tindih dengan sub-masalah yang lebih kecil untuk menghindari perhitungan ulang.

Properti Pemrograman Dinamis

  • Sebuah instance dipecahkan menggunakan solusi untuk instance yang lebih kecil.
  • Solusi untuk instance yang lebih kecil mungkin diperlukan beberapa kali, jadi simpan hasilnya dalam sebuah tabel.
  • Jadi setiap instance yang lebih kecil diselesaikan hanya satu kali.
  • Ruang tambahan digunakan untuk menghemat waktu.
Sabir Al Fateh
sumber
4

Saya juga sangat baru dalam Dynamic Programming (algoritma yang kuat untuk jenis masalah tertentu)

Dengan kata paling sederhana, anggap saja pemrograman dinamis sebagai pendekatan rekursif dengan menggunakan pengetahuan sebelumnya

Pengetahuan sebelumnya adalah yang terpenting di sini, Lacak solusi sub-masalah yang sudah Anda miliki.

Pertimbangkan ini, contoh paling mendasar untuk dp dari Wikipedia

Menemukan urutan fibonacci

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

Mari kita memecah panggilan fungsi dengan mengatakan n = 5

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Secara khusus, fib (2) dihitung tiga kali dari awal. Dalam contoh yang lebih besar, lebih banyak nilai fib, atau sub-masalah, dihitung ulang, yang mengarah ke algoritma waktu eksponensial.

Sekarang, mari kita coba dengan menyimpan nilai yang sudah kita temukan dalam struktur data katakanlah Peta

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

Di sini kita menyimpan solusi sub-masalah di peta, jika kita belum memilikinya. Teknik menyimpan nilai-nilai yang sudah kami hitung ini disebut sebagai Memoisasi.

Akhirnya, Untuk suatu masalah, pertama-tama cobalah untuk menemukan status (kemungkinan sub-masalah dan coba pikirkan pendekatan rekursi yang lebih baik sehingga Anda dapat menggunakan solusi sub-masalah sebelumnya menjadi lebih lanjut).

Aman Singh
sumber
Rip-off langsung dari Wikipedia. Diturunkan !!
solidak
3

Pemrograman dinamis adalah teknik untuk memecahkan masalah dengan sub masalah yang tumpang tindih. Algoritma pemrograman dinamis memecahkan setiap sub masalah hanya sekali dan kemudian Menyimpan jawabannya dalam tabel (array). Menghindari pekerjaan komputasi ulang jawaban setiap kali masalah sub ditemui. Gagasan mendasar dari pemrograman dinamis adalah: Hindari menghitung hal yang sama dua kali, biasanya dengan menyimpan tabel hasil yang diketahui dari sub masalah.

Tujuh langkah dalam pengembangan algoritma pemrograman dinamis adalah sebagai berikut:

  1. Membangun properti rekursif yang memberikan solusi untuk contoh masalah.
  2. Mengembangkan algoritma rekursif sesuai properti rekursif
  3. Lihat apakah contoh masalah yang sama sedang dipecahkan lagi dan lagi dalam panggilan rekursif
  4. Kembangkan algoritma rekursif yang direkam
  5. Lihat pola dalam menyimpan data dalam memori
  6. Ubah algoritma rekursif yang direkam menjadi algoritma berulang
  7. Optimalkan algoritma iteratif dengan menggunakan penyimpanan sesuai kebutuhan (optimisasi penyimpanan)
Adnan Qureshi
sumber
Apakah 6. Convert the memoized recursive algorithm into iterative algorithmlangkah wajib? Ini berarti bahwa bentuk akhirnya adalah non-rekursif?
truthadjustr
tidak wajib, opsional
Adnan Qureshi
Tujuannya adalah untuk mengganti algoritma rekursif yang digunakan untuk menyimpan data dalam memori dengan iterasi atas nilai-nilai yang disimpan karena solusi iteratif menyimpan pembuatan stack fungsi untuk setiap panggilan rekursif yang dilakukan.
David C. Rankin
1

singkatnya perbedaan antara memoisasi rekursi dan pemrograman Dinamis

Pemrograman dinamis sesuai dengan namanya menggunakan nilai yang dihitung sebelumnya untuk secara dinamis membangun solusi baru berikutnya

Di mana menerapkan pemrograman dinamis: Jika solusi Anda didasarkan pada substruktur yang optimal dan sub masalah yang tumpang tindih, maka dalam hal itu menggunakan nilai yang dihitung sebelumnya akan berguna sehingga Anda tidak perlu menghitungnya kembali. Ini adalah pendekatan dari bawah ke atas. Misalkan Anda perlu menghitung fib (n) dalam hal itu yang perlu Anda lakukan adalah menambahkan nilai terhitung sebelumnya dari fib (n-1) dan fib (n-2)

Rekursi: Pada dasarnya membagi masalah Anda menjadi bagian yang lebih kecil untuk menyelesaikannya dengan mudah tetapi perlu diingat itu tidak menghindari perhitungan ulang jika kita memiliki nilai yang sama dihitung sebelumnya dalam panggilan rekursi lainnya.

Memoisasi: Pada dasarnya menyimpan nilai rekursi yang dihitung lama dalam tabel dikenal sebagai memoisasi yang akan menghindari komputasi ulang jika sudah dihitung oleh beberapa panggilan sebelumnya sehingga nilai apa pun akan dihitung satu kali. Jadi sebelum menghitung kita memeriksa apakah nilai ini sudah dihitung atau belum jika sudah dihitung maka kita mengembalikan yang sama dari tabel alih-alih menghitung ulang. Ini juga merupakan pendekatan top-down

Berusaha keras
sumber
-2

Berikut ini adalah contoh sederhana kode python dari Recursive, Top-down, Bottom-uppendekatan untuk seri Fibonacci:

Rekursif: O (2 n )

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

Top-down: O (n) Efisien untuk input yang lebih besar

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

Bottom-up: O (n) Untuk kesederhanaan dan ukuran input yang kecil

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))
0xAliHn
sumber
Kasus pertama TIDAK memiliki waktu berjalan n ^ 2, kompleksitas waktunya adalah O (2 ^ n): stackoverflow.com/questions/360748/…
Sam
diperbarui terima kasih. @ Sam
0xAliHn