Quelle est la différence entre l'approche ascendante et l'approche descendante ?

Question

El ascendant (à la programmation dynamique) consiste à examiner d'abord les "petits" sous-problèmes, puis à résoudre les grands sous-problèmes en utilisant la solution des petits problèmes.

El de haut en bas consiste à résoudre le problème de "manière naturelle" et à vérifier si vous avez déjà calculé la solution du sous-problème.

Je suis un peu perdu. Quelle est la différence entre ces deux-là ?

Answer 1

Les problèmes de programmation dynamique peuvent être résolus à l'aide d'approches ascendantes ou descendantes.

En général, l'approche ascendante utilise la technique de la tabulation, tandis que l'approche descendante utilise la technique de la récursion (avec mémorisation).

Mais vous pouvez aussi avoir des approches ascendantes et descendantes en utilisant la récursion comme indiqué ci-dessous.

De bas en haut : Commencez par la condition de base et passez la valeur calculée jusqu'à présent de manière récursive. En général, il s'agit de récursions de queue.

int n = 5;
fibBottomUp(1, 1, 2, n);

private int fibBottomUp(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibBottomUp(j, i + j, count + 1, n);
}

De haut en bas : Commencer par la condition finale et obtenir récursivement le résultat de ses sous-problèmes.

int n = 5;
fibTopDown(n);

private int fibTopDown(int n) {
    if (n <= 1) return 1;
    return fibTopDown(n - 1) + fibTopDown(n - 2);
}

Answer 2

L'approche descendante utilise la récursion pour appeler les sous-problèmes encore et encore.
alors que l'approche ascendante utilise l'unique sans appeler personne et est donc plus efficace.

Answer 3

Voici la solution basée sur le DP pour le problème de la distance d'édition, qui est descendante. J'espère qu'elle vous aidera également à comprendre le monde de la programmation dynamique :

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();

     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

Vous pouvez penser à son implémentation récursive chez vous. C'est assez bon et stimulant si vous n'avez jamais résolu quelque chose de ce genre auparavant.