La programmation dynamique est une méthode algorithmique qui optimise la résolution de problèmes en les décomposant en sous-problèmes chevauchants, dont les solutions sont stockées pour éviter les recalculs. En C++, elle est couramment mise en œuvre à l'aide de tableaux pour mémoriser les états intermédiaires.

Calcul du nombre de chemins les plus courts sur une grille

Problème : déterminer le nombre de chemins de longueur minimale pour se déplacer d'un point A (1,1) à un point B (n,m) sur une grille, en n'autorisent que des pas vers la droite ou vers le bas.

Solution : utiliser un tableau DP où chaque cellule (i,j) stocke le nombre de chemins y menant. La relation de récurrence est la somme des chemins depuis la cellule au-dessus (i-1,j) et celle à gauche (i,j-1), avec la condition initiale dp[1][1] = 1.

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int lignes, colonnes;
    cin >> lignes >> colonnes;

    // Tableau pour stocker les nombres de chemins
    long long compteurChemins[505][505];
    memset(compteurChemins, 0, sizeof(compteurChemins));

    // Initialisation du point de départ
    compteurChemins[1][1] = 1;

    // Remplissage du tableau par programmation dynamique
    for (int i = 1; i <= lignes; i++) {
        for (int j = 1; j <= colonnes; j++) {
            if (i == 1 && j == 1) continue; // Déjà initialisé
            compteurChemins[i][j] = compteurChemins[i-1][j] + compteurChemins[i][j-1];
        }
    }

    cout << compteurChemins[lignes][colonnes] << endl;
    return 0;
}</cstring></iostream>

Problème Luogu P1002 : le cavalier bloqueant le pion

Description : sur un échiquier, un pion part de (0,0) pour atteindre (n,m) en se déplaçant uniquement vers le bas ou la droite. Un cavalier placé en (x,y) contrôle sa position et toutes les cases accessibles en un saut de cavalier. Calculer le nombre de chemins valides pour le pion.

Solution : adapter la programmation dynamique en marquant les cases contrôlées par le cavalier comme inaccessibles, puis appliquer la même logique de propagation des chemins.

#include <iostream>
using namespace std;

int main() {
    int destX, destY, cavalierX, cavalierY;
    cin >> destX >> destY >> cavalierX >> cavalierY;

    // Ajustement des indices pour une gestion plus facile (base 1)
    destX++; destY++; cavalierX++; cavalierY++;

    // Tableau DP, initialisé à zéro
    long long matriceDP[30][30] = {0};

    // Déplacements possibles du cavalier
    int deltaX[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int deltaY[8] = {1, -1, 2, -2, 2, -2, 1, -1};

    // Marquer les cases contrôlées par le cavalier comme bloquées (-1)
    for (int i = 0; i < 8; i++) {
        int newX = cavalierX + deltaX[i];
        int newY = cavalierY + deltaY[i];
        if (newX >= 1 && newX <= destX && newY >= 1 && newY <= destY) {
            matriceDP[newX][newY] = -1;
        }
    }

    // Bloquer la position du cavalier elle-même
    matriceDP[cavalierX][cavalierY] = -1;

    // Initialisation : le point (1,0) a un chemin pour amorcer le calcul
    matriceDP[1][0] = 1;

    // Remplissage du tableau avec gestion des cases bloquées
    for (int i = 1; i <= destX; i++) {
        for (int j = 1; j <= destY; j++) {
            if (matriceDP[i][j] == -1) {
                matriceDP[i][j] = 0; // Case inaccessible
            } else {
                matriceDP[i][j] = matriceDP[i-1][j] + matriceDP[i][j-1];
            }
        }
    }

    cout << matriceDP[destX][destY] << endl;
    return 0;
}</iostream>