Explication de la solution de programmation dynamique

Question

C'est le problème: avec un nombre de briques n compris entre 3 et 200, renvoyer le nombre d'escaliers différents qui peuvent être construits. Chaque type d'escalier doit comporter deux étapes ou plus. Aucune étape ne doit être à la même hauteur - chaque étape doit être inférieure à la précédente. Toutes les étapes doivent contenir au moins une brique. La hauteur d'une marche est classée comme la quantité totale de briques qui composent cette marche. Par exemple, lorsque N = 3, vous avez seulement 1 choix de la façon de construire l'escalier, avec la première étape ayant une hauteur de 2 et la seconde étape ayant une hauteur de 1: (# indique une brique)

# 
## 
21 

lorsque N = 4, vous encore que 1 ont le choix d'escalier:

# 
# 
## 
31 

Mais quand N = 5, il y a deux façons dont vous pouvez construire un escalier des briques données. Les deux escaliers peuvent avoir des hauteurs (4, 1) ou (3, 2), comme indiqué ci-dessous:

# 
# 
# 
## 
41 

# 
## 
## 
32 

J'ai trouvé une solution en ligne, mais je ne comprends pas tout à fait intuitivement la solution de programmation dynamique.

public class Answer { 

    static int[][] p = new int[201][201]; 

    public static void fillP() { 
     p[1][1] = 1; 
     p[2][2] = 1; 

     for (int w = 3; w < 201 ; w++) { 
      for (int m = 1; m <= w; m++) { 
       if (w-m == 0) { 

        p[w][m] = 1 + p[w][m-1]; 

       } else if (w-m < m) { 

        p[w][m] = p[w-m][w-m] + p[w][m-1]; 

       } else if (w-m == m) { 
        p[w][m] = p[m][m-1] + p[w][m-1]; 

       } else if (w-m >m) { 

        p[w][m] = p[w-m][m-1] + p[w][m-1]; 
       } 

      } 
     } 
    } 

    public static int answer(int n) { 

     fillP(); 
     return p[n][n] - 1; 

    } 

} 

En particulier, comment pourrait-on trouver les relations entre chaque entrée successive dans le tableau?

Answer 1

Ceci est une question très intéressante. Tout d'abord, nous allons essayer de comprendre les recurrence relation:

Si nous avons construit actuellement une étape de hauteur h et nous avons b briques de gauche à utiliser, le nombre de façons que nous pourrions terminer l'escalier d'ici est égale à la somme de tous les façons dont nous pouvons compléter l'escalier avec l'étape suivante de hauteur h' et b - h' briques, pour 0 < h' < h. Une fois que nous avons cette relation de récurrence, nous pouvons concevoir une solution récursive; Cependant, à son état actuel, la solution s'exécute en temps exponentiel. Donc, nous avons juste besoin de « cache » nos résultats:

import java.util.Scanner; 

public class Stairs { 
    static int LIMIT = 200; 
    static int DIRTY = -1; 
    static int[][] cache = new int[LIMIT + 2][LIMIT + 2]; 

    public static void clearCache() { 
    for (int i = 0; i <= LIMIT + 1; i++) { 
     for (int j = 0; j <= LIMIT + 1; j++) { 
     // mark cache as dirty/garbage values 
     cache[i][j] = DIRTY; 
     } 
    } 
    } 

    public static int numberOfStaircases(int level, int bricks, int steps) { 
    // base cases 
    if (bricks < 0) return 0; 
    if (bricks == 0 && steps >= 2) return 1; 

    // only compute answer if we haven't already 
    if (cache[level][bricks] == DIRTY) { 
     int ways = 0; 
     for (int nextLevel = level - 1; nextLevel > 0; nextLevel--) { 
     ways += numberOfStaircases(nextLevel, bricks - nextLevel, steps + 1); 
     } 
     cache[level][bricks] = ways; 
    } 

    return cache[level][bricks]; 
    } 

    public static int answer(int n) { 
    clearCache(); 
    return numberOfStaircases(n + 1, n, 0); 
    } 

    public static void main(String[] args) { 
    Scanner scanner = new Scanner(System.in); 
    int n = scanner.nextInt(); 
    System.out.println(answer(n)); 
    } 
} 

à partir du code que vous avez fourni, il semble que si l'auteur est allé un pas plus loin et a remplacé la solution récursive avec une version purement itérative. Cela signifie que l'auteur a fait un bottom-up solution rather than a top-down solution.

On pourrait aussi aborder le problème plus mathématiquement:

How many distinct non-trivial integer partitions does n have?

Donc, pour n = 6, nous avons: 5 + 1, 4 + 2, 3 + 2 + 1. Donc answer(6) = 3. Chose intéressante, Euler proved que le nombre de partitions entières distinctes pour un n donné est toujours le même que le nombre de partitions entières impaires non nécessairement distinctes.

(En note, je sais d'où vient cette question Bonne chance!)