Étant donné une grille de taille m × n, chaque cellule contenant soit une case vide (0) soit un obstacle (1), il s'agit de calculer le nombre de chemins distincts permettant de rejoindre le coin inférieur droit depuis le coin supérieur gauche, en se déplaçant uniquement vers la droite ou vers le bas.

Approche par programmation dynamique

On note dp[i][j] le nombre de chemins atteignant la cellule (i, j). Comme on ne peut venir que par le haut ou par la gauche, la relation de récurrence est la suivante :

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

Lorsqu'une cellule contient un obstacle, elle devient inatteignable et on impose dp[i][j] = 0. Cette règle vaut égalmeent pour la première ligne et la première colonne : dès qu'un obstacle apparaît, toutes les cellules ultérieures de cette ligne ou colonne reçoivent 0.

Implémentation 2D compacte

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int h = grid.size();
        int w = grid[0].size();
        vector<vector<int>> dp(h, vector<int>(w, 0));

        dp[0][0] = (grid[0][0] == 0) ? 1 : 0;

        for (int i = 1; i < h; ++i)
            dp[i][0] = (grid[i][0] == 0) ? dp[i - 1][0] : 0;

        for (int j = 1; j < w; ++j)
            dp[0][j] = (grid[0][j] == 0) ? dp[0][j - 1] : 0;

        for (int i = 1; i < h; ++i)
            for (int j = 1; j < w; ++j)
                dp[i][j] = (grid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;

        return dp[h - 1][w - 1];
    }
};

Optimisation de l'espace avec un seul tableau

Le calcul d'une ligne ne dépend que de la ligne précédente et des cellules déjà parcourues sur la ligne courante. On peut donc se contenter d'un seul vecteur dp de longueur w, actualisé ligne par ligne.

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int h = grid.size();
        int w = grid[0].size();
        vector<int> dp(w, 0);
        dp[0] = 1;

        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (grid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[w - 1];
    }
};

Complxeité

• Complexité temporelle : O(m × n), chaque cellule étant traitée une seule fois.
• Complexité spatiale : O(m × n) pour la version 2D, et O(n) pour la version optimisée.