Notas de estudio de algoritmos (8): conceptos básicos de programación dinámica

Qué es la programación dinámica, qué problemas puede resolver la programación dinámica como medio, la clasificación de la programación dinámica y la clasificación de problemas específicos que las clasificaciones específicas pueden resolver.

Programación dinámica:

Es un paradigma algorítmico importante que descompone un problema en una serie de subproblemas más pequeños y evita cálculos repetidos al almacenar soluciones de subproblemas, lo que mejora en gran medida la eficiencia del tiempo.

Se introducen problemas para comprender la programación dinámica:

Este problema se introduce a través del caso de subir escaleras. Dada una escalera con n escalones en total, puedes subir 1 o 2 escalones en cada escalón. ¿Cuántas opciones hay para subir a la cima del edificio?

Análisis: (retroceso violento)

El objetivo de esta pregunta es encontrar el número de soluciones,Podemos considerar agotar exhaustivamente todas las posibilidades retrocediendo . Específicamente, imagine subir escaleras como un proceso de selección de múltiples rondas: comenzar desde el suelo, elegir uno o dos escalones en cada ronda, agregar 1 al número de opciones cada vez que llegue a la cima de las escaleras y aumentar el número de opciones cuando Llegas a lo alto de las escaleras.

ejemplo de código：


# 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] ;
}

Búsqueda brutal:

Los algoritmos de retroceso generalmente no desmantelan explícitamente el problema, sino que lo tratan como una serie de pasos de toma de decisiones y buscan todas las soluciones posibles mediante heurísticas y poda.

Podemos intentar analizar esta cuestión desde la perspectiva de la descomposición del problema. Supongamos que hay soluciones dp [i] para subir al nivel i-ésimo, entonces dp [i] es el problema original y sus subproblemas incluyen:

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

Como solo podemos subir 1 o 2 escalones en cada ronda, cuando nos paramos en la i-ésima escalera, solo pudimos pararnos en los escalones i-1 o i-2 de la ronda anterior. En otras palabras, solo podemos pasar del nivel i-1 o i-2 al nivel i-ésimo.

De esto, podemos sacar una inferencia importante: el número de planes que han subido al nivel i-1 más el número de planes que han subido al nivel i-2 es igual al número de planes que han subido al i -ésimo nivel. La fórmula es la siguiente:

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

Esto significa que existe una relación recursiva en el problema de escalada de edificios y el problema original se puede resolver construyendo las soluciones de los subproblemas.

Ejemplo de código DFS: (búsqueda)


# 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) ;
}

Árbol recursivo generado por recursividad violenta.：

Para resolver el problema de duplicación mencionado anteriormente en el árbol recursivo, se puede utilizar el método de búsqueda de memoria para eliminar una gran cantidad de subárboles idénticos que se construyen repetidamente, mejorando así la eficiencia del cálculo. (subproblemas superpuestos）

Búsqueda memorizada:

Para calcular todos los subproblemas superpuestos solo una vez, debe declarar una matriz nem para registrar la solución de cada subproblema y podar los subproblemas superpuestos durante el proceso de búsqueda.

Cuando se calcula dp[i] por primera vez, se registra en nem[i] para su uso posterior.
Cuando se vuelve a calcular dp [i], el resultado se obtiene directamente en nem [i] para evitar cálculos repetidos de subproblemas.

Ejemplo de código:


# 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) ; 
}

Después de la memorización, todos los subproblemas superpuestos se calculan solo una vez y la complejidad del tiempo se optimiza a O (n).

Programación dinámica:

La búsqueda memorizada es un método "de arriba a abajo". Partimos del problema original (nodo raíz) y descomponemos recursivamente los subproblemas más grandes en subproblemas más pequeños hasta resolver el subproblema más pequeño conocido (nodo hoja). . Luego, las soluciones a los subproblemas se recopilan capa por capa mediante un retroceso para construir una solución al problema original.

Por el contrario, la programación dinámica es un enfoque "de abajo hacia arriba": comienza con una solución al subproblema más pequeño y construye iterativamente soluciones para subproblemas más grandes hasta obtener una solución al problema original.

Dado que la programación dinámica no incluye un proceso de retroceso, solo debe implementarse mediante iteración de bucle sin utilizar recursividad.

Ejemplo de código: (programación dinámica, comenzando desde el subproblema más pequeño)


# 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] ;
}

Proceso de ejecución (programación dinámica):

Análisis: (programación dinámica)

Al igual que el algoritmo de retroceso, la programación dinámica también utiliza el concepto de "estado" para representar una etapa específica de la resolución del problema. Cada estado corresponde a un subproblema y la solución óptima local correspondiente. Ejemplo: El estado del problema de subir escaleras se define como el orden i de la escalera actual.

Con base en lo anterior, podemos resumir los términos comunes para términos dinámicos:

La matriz dp se llama {tabla dp}, dp[i] representa la solución al subproblema correspondiente al estado i
El estado correspondiente al subproblema mínimo (la primera y segunda escalera) se llama estado inicial.
La fórmula recursiva dp[i] = dp[i-1] + dp[i-2] se llama ecuación de estado.

Optimización del espacio:

dp[i] solo está relacionado con dp[i-1] y dp[i-2]

En lugar de utilizar una matriz para almacenar las soluciones de todos los subproblemas, sólo se necesitan dos variables para desplazarse hacia adelante.

Ejemplo de código:


# 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 ;
}

Análisis:

Se omite el espacio ocupado por la matriz dp y la complejidad del espacio se reduce de O (n) a O (1)

En los problemas de programación dinámica, el estado actual solo está relacionado con un número limitado de estados anteriores. En este momento, solo podemos retener los estados necesarios y ahorrar espacio en la memoria mediante la "reducción de dimensionalidad". . Esta técnica de optimización del espacio se denomina "variables rodantes" o "matrices rodantes".

Compartir tecnología