Erklärung der dynamischen Programmierlösung

Question

Das ist das Problem: Geben Sie für eine Anzahl von Ziegeln n zwischen 3 und 200 die Anzahl der verschiedenen Treppen, die gebaut werden können, zurück. Jede Art von Treppe sollte aus 2 oder mehr Stufen bestehen. Keine zwei Schritte dürfen auf gleicher Höhe sein - jeder Schritt muss niedriger sein als der vorherige. Alle Schritte müssen mindestens einen Baustein enthalten. Die Höhe eines Schrittes wird als die Gesamtmenge der Steine, die diesen Schritt ausmachen, klassifiziert.

Zum Beispiel, wenn N = 3, haben Sie nur 1 Wahl, wie man die Treppe baut, wobei der erste Schritt eine Höhe von 2 hat und der zweite Schritt eine Höhe von 1: (# bedeutet Ziegel)

# 
## 
21 

wenn N = 4, haben Sie immer noch nur 1 Treppe Wahl:

# 
# 
## 
31 

Aber wenn N = 5 gibt zwei Möglichkeiten, können Sie eine Treppe aus den gegebenen Ziegeln bauen. Die beiden Treppen können Höhen haben (4, 1) oder (3, 2), wie unten dargestellt:

# 
# 
# 
## 
41 

# 
## 
## 
32 

ich eine Lösung gefunden online, aber ich weiß nicht ganz intuitiv die dynamische Programmierlösung verstehen.

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; 

    } 

} 

Insbesondere, wie würde man die Beziehungen zwischen jedem aufeinanderfolgenden Eintrag im Array kommen?

Answer 1

Dies ist eine sehr interessante Frage. Lassen Sie uns zuerst versuchen, das verstehen recurrence relation:

Wenn wir zur Zeit einen Schritt der Höhe h gebaut und wir haben b Steine ​​zu verwenden, links, die Anzahl der Möglichkeiten konnten wir die Treppe vervollständigen von hier gleich der Summe aller ist Möglichkeiten, wie wir die Treppe mit dem nächsten Schritt der Höhe h' und b - h' Ziegel, für 0 < h' < h abschließen können.

Sobald wir diese Wiederholungsbeziehung haben, können wir eine rekursive Lösung entwickeln; Im aktuellen Zustand läuft die Lösung jedoch in exponentieller Zeit. Also, wir müssen „Cache“ unsere Ergebnisse nur:

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)); 
    } 
} 

Aus dem Code, den Sie zur Verfügung gestellt, so scheint es, als ob der Autor ging noch einen Schritt weiter und ersetzt die rekursive Lösung mit einer rein iterativen Version. Dies bedeutet, dass der Autor eine bottom-up solution rather than a top-down solution gemacht hat.

Wir könnten auch das Problem mathematisch nähern:

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

Also für n = 6, haben wir: 5 + 1, 4 + 2, 3 + 2 + 1. Also answer(6) = 3. Interessanterweise ist Euler proved, dass die Anzahl der verschiedenen ganzzahligen Partitionen für eine gegebene n immer die gleiche wie die Anzahl der nicht unbedingt unterschiedlichen ungeraden Ganzzahl Partitionen ist.

(Als Randbemerkung, ich weiß, wo diese Frage kommt. Viel Glück!)