Catatan Studi Algoritma (8) - Dasar-dasar Pemrograman Dinamis

Apa itu pemrograman dinamis, masalah apa yang dapat dipecahkan oleh pemrograman dinamis, klasifikasi pemrograman dinamis, dan klasifikasi masalah spesifik yang dapat diselesaikan oleh klasifikasi spesifik.

Pemrograman dinamis:

Ini adalah paradigma algoritma penting yang menguraikan masalah menjadi serangkaian sub-masalah yang lebih kecil dan menghindari penghitungan berulang dengan menyimpan solusi sub-masalah, sehingga sangat meningkatkan efisiensi waktu.

Masalah dalam memahami pemrograman dinamis diperkenalkan:

Soal ini muncul melalui kasus menaiki tangga. Diberikan sebuah tangga yang jumlah anak tangganya sebanyak n, maka anda dapat menaiki 1 atau 2 anak tangga pada setiap anak tangga. Berapa banyak pilihan yang ada untuk naik ke puncak gedung?

Analisis: (mundur dengan kekerasan)

Tujuan dari pertanyaan ini adalah untuk menemukan jumlah solusi,Kita dapat mempertimbangkan untuk menghabiskan semua kemungkinan secara mendalam dengan melakukan kemunduran . Secara khusus, bayangkan menaiki tangga sebagai proses seleksi multi-putaran: mulai dari tanah, memilih satu atau dua langkah setiap putaran, menambahkan 1 ke jumlah pilihan setiap kali Anda mencapai puncak tangga, dan menambah jumlah pilihan saat Anda mencapai puncak tangga.

contoh kode：


# python代码示例
def backrack(choices,state,n,res) :
    if state == n :
        res[0] += 1 
    for choice in choices :
        if state + choice > n :
            continue
        backrack(choices,state+choice,n,res)
def climbing_stairs_backrack(n) :
    choices = [1,2]
    state = 0
    res = [0]
    backrack(choices,state,n,res)
    return res[0]
n = int(input())
print(climbing_stairs_backrack(n))


// c++代码示例
void backrack(vector<int> &choices, int state, int n, vector<int> &res)
{
    if (state == n )
    {
        res[0]++ ;
    }
    for (auto &choice : choices)
    {
        if (state + choice > n)
        {
            continue ;
        }
        backrack(choices, state + choice, n, res)
    }
}
 
int climbingStairsBackrack(int n)
{    
    vector<int> choices = {1 , 2 } ;
    int state = 0 ;
    vector<int> res = [0] ;
    backrack(choices, state, n, res) ;
    return res[0] ;
}

Pencarian brutal:

Algoritma backtracking biasanya tidak membongkar masalah secara eksplisit, namun memperlakukan masalah sebagai serangkaian langkah pengambilan keputusan, dan mencari semua solusi yang mungkin melalui heuristik dan pemangkasan.

Kita dapat mencoba menganalisis pertanyaan ini dari perspektif penguraian masalah. Asumsikan bahwa ada solusi dp[i] untuk naik ke level ke-i, maka dp[i] adalah permasalahan awal, dan sub-masalahnya meliputi:

dp[i-1], dp[i-2], dp[1], dp[2]

Karena kita hanya bisa menaiki 1 atau 2 anak tangga dalam setiap putaran, maka ketika kita berdiri di anak tangga ke-i, kita hanya bisa berdiri di anak tangga ke-i-1 atau i-2 pada putaran sebelumnya. Dengan kata lain, kita hanya dapat berpindah dari level ke-i-1 atau ke-i-2 ke level ke-i.

Dari sini kita dapat menarik kesimpulan penting: banyaknya plan yang naik ke level i-1 ditambah banyaknya plan yang naik ke level i-2 sama dengan banyaknya plan yang naik ke level i. tingkat -th. Rumusnya adalah sebagai berikut:

dp[i] = dp[i-1] + dp[i-2]

Artinya terdapat hubungan rekursif dalam masalah pendakian gedung, dan masalah awal dapat diselesaikan dengan mengkonstruksi solusi dari sub-masalah tersebut.

Contoh kode Dfs: (pencarian)


# python 代码示例
def dfs(i : int) -> int :
    if i == 1 or i == 2 :
        return i
    count = dfs(i - 1) + dfs(i - 2)
    return count
def climbing_stairs_dfs(n : int) -> int :
    retunr dfs(n)


// c++ 代码示例
int dfs(int i)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    int count = dfs(i - 1) + dfs(i - 2);
    return count ;
}
int climbingStairsDFS(int n)
{
    retunr dfs(n) ;
}

Pohon rekursif dihasilkan oleh rekursi kekerasan：

Untuk mengatasi masalah duplikasi pohon rekursif yang disebutkan di atas, metode pencarian memori dapat digunakan untuk menghapus sejumlah besar subpohon identik yang dibangun berulang kali, sehingga meningkatkan efisiensi perhitungan. (submasalah yang tumpang tindih）

Pencarian yang dihafal:

Untuk menghitung semua submasalah yang tumpang tindih hanya satu kali, Anda perlu mendeklarasikan array nem untuk mencatat solusi setiap submasalah, dan memangkas submasalah yang tumpang tindih selama proses pencarian.

Ketika dp[i] dihitung untuk pertama kalinya, ia dicatat dalam nem[i] untuk penggunaan selanjutnya.
Ketika dp[i] dihitung lagi, hasilnya diperoleh langsung di nem[i] untuk menghindari penghitungan sub-masalah yang berulang.

Contoh kode:


# python 代码示例
def dfs(i : int, mem : list[int]) -> int :
    if i == 1 or i == 2 :
        return i
    if mem[i] != -1 :
        return mem[i]
    count = dfs(i - 1, mem) + dfs(i - 2, mem)
    # 记录dfs(i)
    mem[i] = count
    return count
def climbing_stairs_dfs_mem(n : int) -> int :
    mem = [-1] * (n + 1)
    return dfs(n, mem)


// c++ 代码示例
int dfs(int i, vector<int> &mem)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    if (mem != -1)
    {
        return mem[i] ;
    }
    int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
    mem[i] = count ;
    return count ;
}
int climbingStairsDFSMem(int n)
{
    vector<int> mem(n + 1, -1) ;
    return dfs(n, mem) ; 
}

Setelah memoisasi, semua submasalah yang tumpang tindih dihitung hanya satu kali, dan kompleksitas waktu dioptimalkan menjadi O(n).

Pemrograman dinamis:

Pencarian memo adalah metode "atas-ke-bawah". Kita mulai dari masalah awal (simpul akar) dan secara rekursif menguraikan sub-masalah yang lebih besar menjadi sub-masalah yang lebih kecil hingga kita menyelesaikan sub-masalah terkecil yang diketahui (simpul daun). . Setelah itu, solusi terhadap sub-masalah dikumpulkan lapis demi lapis melalui penelusuran mundur untuk membangun solusi terhadap masalah awal.

Sebaliknya, pemrograman dinamis adalah pendekatan "dari bawah ke atas": dimulai dengan solusi terhadap submasalah terkecil dan secara iteratif membangun solusi untuk submasalah yang lebih besar hingga solusi terhadap masalah awal diperoleh.

Karena pemrograman dinamis tidak menyertakan proses backtracking, maka hanya perlu diimplementasikan menggunakan iterasi loop tanpa menggunakan rekursi.

Contoh kode: (pemrograman dinamis, dimulai dari submasalah terkecil)


# python 代码示例
def clibing_stairs_dp(n) :
    if n == 1 or n == 2 :
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3,n + 1) :
        dp[i] = dp[i-1] + dp[i- 2]
    return dp[n]


// c++ 代码示例
 
int climbingStairsDP(int n) 
{
    if (n == 1 || n == 2)
    {
        retunr n ;
    }
    vector<int> dp(n + 1, -1) ;
    dp[1] = 1 ;    
    dp[2] = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        dp[i] = dp[i - 1] + dp[i- 2] ;
    }
    return dp[n] ;
}

Proses eksekusi (pemrograman dinamis):

Analisis: (pemrograman dinamis)

Mirip dengan algoritma backtracking, pemrograman dinamis juga menggunakan konsep "keadaan" untuk mewakili tahap tertentu dari pemecahan masalah. Setiap keadaan berhubungan dengan sub-masalah dan solusi optimal lokal yang sesuai. Contoh: Status soal menaiki tangga didefinisikan sebagai urutan i dari tangga saat ini.

Berdasarkan penjelasan di atas, kita dapat meringkas istilah umum untuk istilah dinamis:

Array dp disebut {dp table}, dp[i] mewakili solusi untuk sub-masalah yang sesuai dengan keadaan i
Keadaan yang sesuai dengan submasalah minimum (tangga pertama dan kedua) disebut keadaan awal
Rumus rekursif dp[i] = dp[i-1] + dp[i-2] disebut persamaan keadaan

Pengoptimalan ruang:

dp[i] hanya terkait dengan dp[i-1] dan dp[i-2]

Daripada menggunakan array untuk menyimpan solusi untuk semua submasalah, hanya diperlukan dua variabel untuk menggulir ke depan.

Contoh kode:


# python 代码示例
def clibing_stairs_dp_comp(n) :
    if n == 1 or n == 2 :
        return n
    a, b = 1, 2
    for _ in range(3, n + 1) :
        a, b = b , a + b
    return b


// c++ 代码示例
int climbingStairsComp(int n) 
{
    if (n == 1 || n == 2)
    {
        return n ;
    }
    int a = 1 , b = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        int temp = b ;
        b = a + b ;
        a = temp ;
    }
    return b ;
}

Analisis:

Ruang yang ditempati oleh array dp dihilangkan, dan kompleksitas ruang dikurangi dari O(n) menjadi O(1)

Dalam masalah pemrograman dinamis, keadaan saat ini hanya terkait dengan sejumlah keadaan sebelumnya. Saat ini, kita hanya dapat mempertahankan keadaan yang diperlukan dan menghemat ruang memori melalui "pengurangan dimensi". . Teknik pengoptimalan ruang ini disebut "variabel bergulir" atau "array bergulir".

Berbagi teknologi