ARTES #023

##ARTES 023 este es el articulo 23

Pregunta sobre el algoritmo del algoritmo

72. Editar distancia

Dificultad Difícil

Dadas dos palabras palabra1 y palabra2, encuentre el número mínimo de operaciones necesarias para convertir palabra1 en palabra2.

Tiene permitidas las siguientes 3 operaciones en una palabra:

Ejemplo 1:

Ejemplo 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')

Yo mismo no resolví completamente esta pregunta. Luego busqué la respuesta y descubrí que se necesitaba programación dinámica. Nunca antes había estudiado programación dinámica en profundidad. Aproveché esta oportunidad para estudiarlo detenidamente y descubrí que la programación dinámica realmente no es fácil de entender. Después de leerlo durante dos días, descubrí que acababa de empezar. Al aprender programación dinámica, se recomienda leer primero la “Ilustración del algoritmo”. La explicación de la programación dinámica en la Ilustración de algoritmos es relativamente fácil de entender y luego busque información en Internet que le ayude a comprenderla. La programación dinámica no es algo que se pueda entender de una sola vez. Aún necesitas practicar más.

Con respecto a esta pregunta sobre el algoritmo, ésta está relativamente bien: https://blog.csdn.net/pipisorry/article/details/46383947

Además de la programación dinámica, este problema también se puede resolver de forma recursiva.

Solución

Idioma: 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];
}

Revisión

Este artículo presenta principalmente varios conocimientos clave de programación que los principiantes en programación deben dominar: https://dandan2009.github.io/2019/01/25/the-main-pillars-of-learning-programming/

CONSEJOS

Esta semana resolvimos los principios del cifrado asimétrico, https y firmas de iOSAPP: https://dandan2009.github.io/2019/01/24/certificate-rsa/

Compartir

Como desarrollador de iOS, aún debes seguir practicando algoritmos. Además de los algoritmos, todavía es necesario ponerse al día con los conocimientos básicos relacionados con la informática. Aunque en la mayor parte del desarrollo utilizamos sistemas directamente encapsulados, rara vez nos encontramos con situaciones en las que escribimos algoritmos y redes nosotros mismos. La razón por la que rara vez lo encuentras es porque todavía estás en la superficie y no profundizas lo suficiente. Por ejemplo, para optimizar iOS, es necesario comprender aspectos relacionados con el sistema operativo y observar algunos códigos excelentes y la implementación del código fuente subyacente. Si no domina los conocimientos básicos de algoritmos y computadoras, encontrará que no se puede optimizar iOS. Por eso creo que cualquier programador debería aprender los conceptos básicos de informática, que son cosas que se imparten en nuestros cursos universitarios, como sistemas operativos, redes informáticas, algoritmos y estructuras de datos. No es que estas cosas sean inútiles, pero todavía estás en la superficie de la programación y no has profundizado en ella.