Apa's perbedaan antara rekursi, memoization & pemrograman dinamis?

Pertimbangkan untuk menghitung deret fibonacci:

Murni rekursi:

int fib(int x)
{
    if (x < 2)
        return 1;

    return fib(x-1) + fib(x-2);
}

hasil di eksponensial jumlah panggilan.

Rekursi dengan memoization/DP:

int fib(int x)
{
    static vector cache(N, -1);

    int& result = cache[x];

    if (result == -1)
    {
        if (x < 2)
            result = 1;
        else
            result = fib(x-1) + fib(x-2);
    }

    return result;
}

Sekarang kita memiliki linier jumlah panggilan pertama kalinya, dan konstan setelah itu.

Di atas metode ini disebut "malas". Kita hitung sebelumnya hal yang pertama kali mereka diminta untuk.

Berikut juga akan dianggap DP, tapi tanpa rekursi:

int fibresult[N];

void setup_fib()
{
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < N; i++)
       fibresult[i] = fibresult[i-1] + fibresult[i-2];
}

int fib(int x) { return fibresult[x]; }

Cara ini dapat digambarkan sebagai "ingin", "pra-tembolok" atau "iteratif". Lebih cepat secara keseluruhan, tetapi kita harus secara manual mencari tahu urutan sub-sub permasalahan yang perlu dihitung dalam. Ini adalah mudah untuk fibonacci, tapi untuk yang lebih kompleks DP masalah ini semakin sulit, dan begitu kita kembali ke malas metode recursive jika itu cukup cepat.

Juga berikut ini tidak rekursi atau DP:

int fib(int x)
{
    int a = 1;
    int b = 1;
    for (int i = 2; i < x; i++)
    {
        a = a + b;
        swap(a,b);
    }
    return b;
}

Menggunakan konstanta ruang dan waktu linier.

Juga saya akan menyebutkan demi kelengkapan ada bentuk tertutup untuk fibonacci yang menggunakan nether rekursi atau DP yang memungkinkan kita untuk menghitung konstanta waktu fibonacci istilah yang menggunakan rumus matematika yang didasarkan pada rasio emas:

http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/

Nah, rekursi+memoization lebih tepatnya tertentu "rasa" dari pemrograman dinamis: pemrograman dinamis sesuai dengan top-down pendekatan.

Lebih tepatnya, ada's tidak ada requrement untuk menggunakan rekursi secara khusus. Setiap divide & menaklukkan solusi dikombinasikan dengan memoization adalah top-down pemrograman dinamis. (Rekursi adalah LIFO rasa membagi & menaklukkan, sementara anda juga dapat menggunakan FIFO membagi & menaklukkan atau jenis lain dari membagi & conquer).

Jadi itu adalah lebih benar untuk mengatakan bahwa

divide & conquer + memoization == top-down dynamic programming

Juga, dari seorang yang sangat formal point of view, jika anda menerapkan membagi & menaklukkan solusi untuk masalah yang tidak menghasilkan berulang-ulang solusi parsial (yang berarti bahwa ada's tidak ada manfaat di memoization), maka anda dapat mengklaim bahwa ini membagi & menaklukkan solusi merosot contoh "pemrograman dinamis".

Namun, pemrograman dinamis adalah konsep yang lebih umum. Pemrograman dinamis dapat menggunakan pendekatan bottom-up, yang berbeda dari membagi & menaklukkan+memoization.

I'm yakin anda dapat menemukan definisi rinci melalui internet. Berikut ini adalah upaya saya untuk menyederhanakan hal.

Rekursi memanggil dirinya lagi.

Dynamic Programming adalah cara untuk memecahkan masalah yang menunjukkan struktur tertentu (optimal sub struktur) di mana masalah dapat dipecah menjadi sub masalah yang mirip dengan masalah asli. Jelas salah satu dapat memanggil rekursi untuk menyelesaikan DP. Tapi itu tidak perlu. Satu dapat memecahkan DP tanpa rekursi.

Memoization adalah cara untuk mengoptimalkan DP algoritma yang bergantung pada rekursi. Intinya adalah untuk tidak memecahkan sub masalah yang telah dipecahkan. Anda dapat melihat ini sebagai cache solusi untuk sub masalah.

Mereka adalah konsep yang berbeda. Mereka tumpang tindih cukup sering, tapi mereka berbeda.

Rekursi terjadi setiap kali sebuah fungsi yang memanggil dirinya sendiri, secara langsung atau tidak langsung. Ini adalah semua.

Contoh:

a -> call a
a -> call b, b -> call c, c -> call a

Dynamic programming adalah ketika anda menggunakan solusi untuk sub-sub permasalahan yang lebih kecil dalam rangka untuk memecahkan masalah yang lebih besar. Ini adalah cara termudah untuk menerapkan secara rekursif karena anda biasanya berpikir tentang solusi tersebut dalam hal fungsi rekursif. Sebuah implementasi berulang biasanya lebih disukai meskipun, karena dibutuhkan sedikit waktu dan memori.

Memoization digunakan untuk mencegah rekursif DP implementasi dari mengambil lebih banyak waktu dari yang dibutuhkan. Sebagian besar kali, DP algoritma yang sama akan digunakan subproblem dalam memecahkan beberapa masalah besar. Dalam implementasi rekursif, ini berarti kita akan menghitung ulang hal yang sama beberapa kali. Memoization menyiratkan menyimpan hasil dari sub-sub permasalahan ini ke meja. Ketika memasuki sebuah pemanggilan rekursif, kita periksa apakah hasilnya ada di tabel: jika ya, kita kembali, jika tidak, kita menghitung itu, menyimpannya di atas meja, dan kemudian kembali.

Rekursi sama sekali tidak ada hubungannya dengan memoization dan pemrograman dinamis; itu adalah benar-benar terpisah konsep.

Jika tidak, ini adalah duplikat pertanyaan: https://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-top-down-vs-bottom-up-approaches