Lorsqu'un problème algorithmique nécessite de tracer deux chemins indépendants sur une matrice, généralement du coin supérieur gauche vers le coin inférieur droit, l'objectif est souvent de maximiser la somme des valeurs collectées. Une contrainte classique stipule que si les deux chemins se croisent sur une même cellule, la valeur de celle-ci ne doit être comptée qu'une seule fois.

Modélisation Quadridimensionnelle

L'approche la plus intuitive consiste à suivre les coordonnées exactes des deux chemins. L'état de la programmation dynamique peut être défini par dp[x1][y1][x2][y2], représantant la valeur maximale obtenue lorsque le premier chemin se trouve en (x1, y1) et le second en (x2, y2).

Bien que fonctionnelle, cette méthode possède une complexité spatiale en $O(N^4)$, ce qui provoque rapidement des dépassements de mémoire pour des grilles de taille importante. Voici une implémentation en C++ modernisée de cette approche, restreignant les états pour éviter que les chemins ne se superposent avant la fin :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int DIM_MAX = 55;
int grille[DIM_MAX][DIM_MAX];
int memo[DIM_MAX][DIM_MAX][DIM_MAX][DIM_MAX];

void resoudre_quatre_dimensions() {
    int nb_lignes, nb_colonnes;
    if (!(cin >> nb_lignes >> nb_colonnes)) return;

    for (int i = 1; i <= nb_lignes; ++i) {
        for (int j = 1; j <= nb_colonnes; ++j) {
            cin >> grille[i][j];
        }
    }

    for (int i = 0; i <= nb_lignes; ++i)
        for (int j = 0; j <= nb_colonnes; ++j)
            for (int k = 0; k <= nb_lignes; ++k)
                for (int l = 0; l <= nb_colonnes; ++l)
                    memo[i][j][k][l] = 0;

    for (int r1 = 1; r1 <= nb_lignes; ++r1) {
        for (int c1 = 1; c1 <= nb_colonnes; ++c1) {
            // Le second chemin est forcé d'être sur une ligne différente
            for (int r2 = r1 + 1; r2 <= nb_lignes; ++r2) {
                int c2 = r1 + c1 - r2;
                if (c2 < 1 || c2 > nb_colonnes) continue;

                int meilleur_predecesseur = max({
                    memo[r1 - 1][c1][r2][c2 - 1],
                    memo[r1 - 1][c1][r2 - 1][c2],
                    memo[r1][c1 - 1][r2 - 1][c2],
                    memo[r1][c1 - 1][r2][c2 - 1]
                });

                memo[r1][c1][r2][c2] = meilleur_predecesseur + grille[r1][c1] + grille[r2][c2];
            }
        }
    }

    int resultat_final = max({
        memo[nb_lignes - 1][nb_colonnes][nb_lignes][nb_colonnes - 1],
        memo[nb_lignes][nb_colonnes - 1][nb_lignes - 1][nb_colonnes]
    });
    
    cout << resultat_final + grille[nb_lignes][nb_colonnes] << "\n";
}

int main() {
    int cas_tests;
    if (cin >> cas_tests) {
        while (cas_tests--) resoudre_quatre_dimensions();
    }
    return 0;
}

Optimisation Spatiale par Invariant de Pas

Pour pallier la lourdeur de l'approche précédente, on peut tirer parti d'une propriété fondamentale : à chaque étape de déplacement (un pas vers la droite ou vers le bas), la somme des coordonnées d'un chemin est constante. Si les deux chemins avancent de manière synchrone, on a toujours l'invariant suivant :

x1 + y1 = x2 + y2 = pas

Cette relation mathématique permet de déduire y1 et y2 si l'on connaît x1, x2 et le nombre de pas effectués. La table de mémoïsation passe ainsi de quatre à trois dimensions : dp[pas][x1][x2]. La complexité spatiale chute drastiquement à $O(N^3)$.

L'implémentation ci-dessous intègre cette optimisation et gère de manière explicite les intersections. Lorsque x1 == x2 (ce qui implique y1 == y2), la valeur de la cellule n'est ajoutée qu'une seule fois pour éviter le double comptage.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int TAILLE_MAX = 110;
int matrice[TAILLE_MAX][TAILLE_MAX];
int dp_opt[TAILLE_MAX * 2][TAILLE_MAX][TAILLE_MAX];

inline int max_de_quatre(int a, int b, int c, int d) {
    return max(max(a, b), max(c, d));
}

void traiter_cas_optimise() {
    int m, n;
    cin >> m >> n;

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> matrice[i][j];
        }
    }

    for (int p = 0; p <= m + n; ++p)
        for (int i = 0; i <= m; ++i)
            for (int j = 0; j <= m; ++j)
                dp_opt[p][i][j] = 0;

    dp_opt[0][1][1] = matrice[1][1];

    int total_pas = m + n - 2;

    for (int pas = 1; pas <= total_pas; ++pas) {
        for (int r1 = 1; r1 <= min(m, pas + 1); ++r1) {
            for (int r2 = 1; r2 <= min(m, pas + 1); ++r2) {
                
                int c1 = pas + 2 - r1;
                int c2 = pas + 2 - r2;

                // Ignorer les états hors des limites de la grille
                if (c1 > n || c2 > n || c1 < 1 || c2 < 1) continue;

                int meilleur_predecesseur = max_de_quatre(
                    dp_opt[pas - 1][r1][r2],
                    dp_opt[pas - 1][r1][r2 - 1],
                    dp_opt[pas - 1][r1 - 1][r2],
                    dp_opt[pas - 1][r1 - 1][r2 - 1]
                );

                if (r1 != r2) {
                    // Chemins sur des cellules distinctes
                    dp_opt[pas][r1][r2] = meilleur_predecesseur + matrice[r1][c1] + matrice[r2][c2];
                } else {
                    // Intersection : la valeur n'est collectée qu'une fois
                    dp_opt[pas][r1][r2] = meilleur_predecesseur + matrice[r1][c1];
                }
            }
        }
    }
    
    cout << dp_opt[total_pas][m][m] << "\n";
}

int main() {
    int t;
    if (cin >> t) {
        while (t--) traiter_cas_optimise();
    }
    return 0;
}

La réduction de dimensionnalité exige une rigueur particulière lors de l'écriture des bornes de boucles. Des erreurs fréquentes surviennent lorsque les indices calculés pour les colonnes dépassent la largeur de la matrice ou deviennent nuls. L'utilisation de conditions de garde strictes (comme c1 > n || c1 < 1) assure la robustesse de l'algorithme face à toutes les configurations géométriques de la grille.