Programação dinâmica §

---

A programação dinâmica é uma técnica poderosa para resolver problemas de otimização ao quebrá-los em subproblemas menores e resolver cada subproblema apenas uma vez, armazenando os resultados para evitar trabalho redundante.

Um exemplo clássico de programação dinâmica é o problema do Caminho Mínimo (ou Caminho Mais Curto) em uma matriz, onde você deve encontrar o caminho de menor custo utilizando a técnica do Canto Noroeste, iniciando do canto superior esquerdo até o canto inferior direito de uma matriz, movendo-se apenas para a direita ou para baixo.

#include <stdio.h>
#include <limits.h>
 
// Função para encontrar o caminho de menor custo em uma matriz
int min(int a, int b) {
    return (a < b) ? a : b;
}
 
int caminhoMinimo(int matriz[3][3], int n) {
    int dp[n][n];
 
    // Inicializa a célula inicial
    dp[0][0] = matriz[0][0];
 
    // Inicializa a primeira linha do array dp
    for (int i = 1; i < n; i++)
        dp[0][i] = dp[0][i - 1] + matriz[0][i];
 
    // Inicializa a primeira coluna do array dp
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i - 1][0] + matriz[i][0];
 
    // Preenche o restante da tabela dp
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = matriz[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
 
    // Retorna o custo mínimo para alcançar o canto inferior direito
    return dp[n - 1][n - 1];
}
 
int main() {
    int matriz[3][3] = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    int n = 3;
 
    printf("Custo mínimo: %d\n", caminhoMinimo(matriz, n));
    return 0;
}

Note

A técnica de programação dinâmica é utilizada aqui para evitar o cálculo repetido de subproblemas. Cada valor na matriz dp representa o custo mínimo para alcançar uma célula específica, e esse valor é calculado apenas uma vez. O problema original é resolvido construindo-se a solução a partir dos subproblemas menores (os caminhos possíveis para cada célula), e cada subproblema é resolvido utilizando os resultados já computados dos subproblemas anteriores.

Referências §

---

https://drive.google.com/file/d/1vGZYPPw7PZuMMqXpjjUkF_kMGTmVv1-r/view?usp=drive_link