16 Exercices Corrigés Programmation dynamique et Diviser pour régner

Dans ce problème, nous supposerons que les deux robots passeront à la rangée suivante en même temps afin qu’ils restent tous les deux dans la même rangée. Ce sera le premier aperçu pour résoudre ce problème.

Comme décrit dans l’énoncé du problème, nous pouvons nous déplacer dans 3 directions (i+1, j-1) , (i+1, j) ou (i+1, j+1). Tous dans la ligne suivante mais avec une colonne différente.

Puisque nous avons 3 directions pour chaque robot, il y a donc à chaque rangée 9 (3 x 3) états vers lesquels nous pouvons nous déplacer. (3 états pour le premier robot et 3 états pour le deuxième robot donc c’est 3 x 3).

Et comme l’indique l’indice, nous devons avoir un tableau DP de 4 lignes. Comme il s’agit d’un tableau à 3 dimensions, il y aura un tableau à 2 dimensions qui sera n * n, c’est-à-dire no. de colonne * no. de colonne. Où la ligne sera définie par la position de la colonne Robot1 et la colonne précisera la position de la colonne Robot2.

Au départ, nous savons que robot1 est à la position 0 et que robot2 est à la position colonne – 1, c’est-à-dire la dernière colonne.

Nous devons remplir dp[0] c’est-à-dire la 1ère ligne et dans cette 1ère ligne, la position de colonne pour le robot sera (0, 2) car 0 signifie la position de colonne pour robot1 et 2 signifie la position de colonne pour robot2 dans la grille.

Lorsque nous remplissons l’espace, nous obtenons la valeur 3 + 1 soit 4

Maintenant, nous devons remplir la 2ème rangée. Et dans la 2ème ligne également, il y aura une matrice n * m. Si nous prenons la position précédente de robot1 comme étant 0, nous avons 3 colonnes dans lesquelles il peut aller dans la ligne suivante, c’est-à-dire col {-1, 0, 1}. Comme col1 est hors limite, nous rejetons ce « -1 » et ne gardons que « 0, 1 »

Et pareil le robot2 est en 2, on peut soit atteindre la col {1, 2, 3}. Comme col3 est hors limite, nous le rejetons « 3 » et ne gardons que « 1, 2 »

Maintenant, lorsque nous créons la combinaison de toutes les colonnes que robot1 et robot2 peuvent être, nous obtenons 4 valeurs et lorsque nous la remplissons, ce sera :

Donc, si nous regardons pour (0, 1) la valeur qui revient sera grid[0][1] + grid[1][1] + prev. Mais pour (1,1) ce sera grid[1][1] + prev.

Si on parle maintenant de code. Prenons dp[row][column][column] notre programmation dynamique. Au début col1=0 et col2=column-1 (emplacement des robots).

Nous avons la solution max=dp[0][col1][col2].

Voici le code permettant de remplir pour chaque valeur croissante de dp[raw][][]

// now comes a part where we need to iterate over each row;
        for(int i = 1; i < row; i++){ // each row starting with 1
            // In this each row of dp, we need to excise our logic picking that particular column, as the starting position
            // we need to loop on all the columns precise in this row
            // as i told there will be n * m column
            for(int c1 = 0; c1 < col; c1++){ 
                for(int c2 = 0; c2 < col; c2++){
                    // now from every column we need to fill the cube; for all the combinations or all the cell we can reach; with respective robot1 & robot2
                    // now we need to 1st take the previous value, that we disucssed
                    int prev = dp[i - 1][c1][c2]; 
                    if(prev >= 0){ // if that the case, we need to perform our operation, if it is a -ve value it means that we haven't reach yet that particular cell. And above that's why we intialize the whole array with -1
                        // Now we need to iterate over all the combinations of column that c1 & c2 can be in. For that we had define a direction array at the top
                        for(int d1: dir){ // for c1 we have the direction "d1" and we iterate over it
                            col1 = d1 + c1; // and column1 will be d1 + c1
                            for(int d2: dir){ // for c2 we have the direction "d2" and we iterate over it
                                col2 = d2 + c2; // and column2 will be d2 + c2
                            // Now we need to check is the new col1 & col2 are in the range of 0 & col. And for that we need to create a new method, which will check is the new col1 & col2 are in the range
                                if(inRange(col1, col) && inRange(col2, col)){
                                    dp[i][col1][col2] = Math.max(dp[i][col1][col2], prev+(col1 == col2 ? grid[i][col1] : (grid[i][col1] + grid[i][col2]))); // if the value are int this range, we need to update the col1 & col2 position in the i'th row
                                    max = Math.max(max, dp[i][col1][col2]); // we need to update the maximum at each step. Taking max of max value & also the new column that we have filled
                                }
                            }
                        }
                    }
                    
                }
            }
        }
        return max; //eturn max at the end

Appelons dp’ l’approche montante. Voici un code mieux optimisé en utilisant une approche descendante du problème d’origine.

dp[k][i][j] indique si les deux robots partent de grid[k][i] et grid[k][j] le nombre total maximum de cerises qu’ils peuvent enfin ramasser. Notez qu’ils ne peuvent se déplacer qu’en bas.

Après avoir rempli dp, la réponse finale est dp[0][0][COL_NUM – 1]

Pour la dernière ligne de grille, on a dp[-1][i][j] = grille[-1][i] si i == j sinon grille[-1][i] + grille[-1][j]. Notez que si 2 robots restent au même endroit, ils ne peuvent ramasser qu’une seule fois.

Pour les autres rangées, nous devons parcourir toutes les combinaisons de directions 3 * 3 qu’ils peuvent choisir dans la couche suivante et trouver le maximum, car pour chaque robot, il y a 3 directions dans lesquelles ils peuvent se déplacer. 

On aura donc le code suivant :

Ce n’est pas très optimal. Voici un code mieux optimisé en python (en 2D avec une approche DFS) :