SENI #023

SENI 023

Ini adalah pasal 23

Pertanyaan algoritma algoritma

72. Edit Jarak

Kesulitan Sulit

Diberikan dua kata kata1 dan kata2, tentukan jumlah operasi minimum yang diperlukan untuk mengubah kata1 menjadi kata2.

Anda memiliki 3 operasi berikut yang diizinkan pada sebuah kata:

Contoh 1:

Contoh 2:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Saya sendiri tidak sepenuhnya menyelesaikan pertanyaan ini. Kemudian saya mencari jawabannya dan menemukan bahwa pemrograman dinamis diperlukan. Saya belum pernah mempelajari pemrograman dinamis secara mendalam sebelumnya. Saya mengambil kesempatan ini untuk mempelajarinya dengan cermat dan menemukan bahwa pemrograman dinamis sangat tidak mudah untuk dipahami. Setelah membacanya selama dua hari, saya menemukan bahwa saya baru saja memulai. Saat mempelajari pemrograman dinamis, disarankan untuk membaca “Ilustrasi Algoritma” terlebih dahulu. Penjelasan pemrograman dinamis pada Ilustrasi Algoritma relatif mudah dipahami, kemudian mencari informasi di Internet untuk membantu Anda memahaminya. Pemrograman dinamis bukanlah sesuatu yang dapat dipahami sekaligus. Anda masih perlu berlatih lebih banyak.

Mengenai pertanyaan algoritma ini, yang ini relatif oke: https://blog.csdn.net/pipisorry/article/details/46383947

Selain pemrograman dinamis, masalah ini juga dapat diselesaikan secara rekursif.

Solusi

Bahasa: C

static inline int min(int a, int b)
{
    return a < b ? a : b;
}

 int minDistance(char* word1, char* word2)
{
    int i, j;
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int *table = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    int **dp = malloc((len1 + 1) * sizeof(int *));
    for (i = 0; i < len1 + 1; i++) {
        dp[i] = table + i * (len2 + 1);
    }
    
    for (i = 0; i < len2 + 1; i++) {
        dp[0][i] = i;
    }
    for (i = 0; i < len1 + 1; i++) {
        dp[i][0] = i;
    }
    
    for (i = 1; i < len1 + 1; i++) {
        for (j = 1; j < len2 + 1; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
            }
            

        }
    }
    return dp[len1][len2];
}

Ulasan

Artikel ini terutama memperkenalkan beberapa pengetahuan pemrograman utama yang harus dikuasai oleh pemula pemrograman: https://dandan2009.github.io/2019/01/25/the-main-pillars-of-learning-programming/

TIPS

Minggu ini kami memilah prinsip enkripsi asimetris, https, dan tanda tangan iOSAPP: https://dandan2009.github.io/2019/01/24/certificate-rsa/

Bagikan

Sebagai pengembang iOS, Anda tetap harus terus berlatih algoritme. Selain algoritma, Anda masih perlu mengejar pengetahuan dasar yang berhubungan dengan komputer. Meskipun dalam sebagian besar pengembangan, kami menggunakan sistem yang dienkapsulasi secara langsung, dan kami jarang menghadapi situasi di mana kami menulis algoritma dan jaringan sendiri. Alasan kenapa kamu jarang menjumpainya adalah karena kamu masih berada di permukaan dan belum menyelam cukup dalam. Misalnya, untuk mengoptimalkan iOS, Anda perlu memahami hal-hal yang berkaitan dengan sistem operasi, dan Anda perlu melihat beberapa kode bagus dan implementasi kode sumber yang mendasarinya. Jika Anda tidak menguasai pengetahuan dasar tentang algoritma dan komputer, Anda akan menemukan bahwa optimasi iOS tidak dapat dilakukan. Jadi menurut saya setiap programmer harus mempelajari dasar-dasar komputer, yang merupakan hal-hal yang ada di mata kuliah universitas kita, seperti sistem operasi komputer, jaringan komputer, algoritma dan struktur data. Bukan berarti hal-hal ini tidak berguna, tetapi Anda masih berada di permukaan pemrograman dan belum mendalaminya.