Wie viele Möglichkeiten für Barcode mit Einschränkung zu begrenzen, beschränken

Question

Dies ist einer der Hausaufgaben von einem Grader ich habe. Ich habe mich seit zwei Tagen mit dieser Frage beschäftigt. Das Thema dreht sich um Dynamische Programmierung und ich habe keine Ahnung, wie ich das verstehen soll.

Das Detail ist das folgende.

Ein Barcode besteht aus schwarzen und weißen vertikalen Linien in unterschiedlicher Anordnung. Der Einfachheit halber verwenden wir eine Kette von "0" und "1", um einen Strichcode zu identifizieren, so dass "0" eine schwarze Linie darstellt, während "1" eine weiße Linie darstellt.

ist ein Barcode somit Fehler sein robust ausgelegt es einige spezifische Regeln zu folgen hat:

1) Ein Barcode muss genau N Linien besteht

nicht mehr sein

2) Es kann als M aufeinander folgende Zeilen gleicher Farbe. Wenn beispielsweise M = 3 ist, ist der Strichcode "01100001" ungültig, da er aus vier aufeinanderfolgenden weißen Zeilen besteht. 1001100 ist jedoch legal.

3) Wir definieren "Farbwechsel" wie folgt. Farbwechsel tritt auf, wenn zwei aufeinanderfolgende Zeilen unterschiedliche Farben haben. Zum Beispiel hat 1001100 3 Farben ändern. Ein Barcode muss genau K Farbwechsel haben.

4) Die erste Zeile ist immer eine schwarze Zeile.

Wir Interesse der Anzahl der möglichen Barcode in Bezug auf gegebene Werte von N in dem Wissen,, M und K.

Eingang Es gibt nur eine Zeile enthält 3 ganze Zahlen N, M und K, wobei 1 < = N, M < = 30 und 0 < = K < = 30

Output Der Ausgang muss enthalten genau eine Zeile mit der Anzahl der möglichen Barcodes.

Zum Beispiel

Eingangs

4 3 1 

Output

3 

Eingang

5 2 2 

Output

3 

Eingangs

7 9 4 

Output

15 

Answer 1

Bei jedem Schritt (die i Barcode) haben wir 2 Möglichkeiten: Entweder wählen sie weiß oder schwarz, hängt dann von diesem Update Ihres Zustand (m und k).

hier ein Pseudo-Java-Code mit Kommentaren, zögern Sie nicht zu fragen, ob etwas nicht klar ist:

static int n,m,k,memo[][][][]; 
    static int dp(int i,int mm,int kk,int last) { 
     if(mm > m || kk > k) return 0; // limitation constrains 
     if(i==n) return kk==k?1:0; // if we build our barcode (i == n), we need to check color changing if it's ok return 1 else return 0 
     if(memo[i][mm][kk][last] != -1) return memo[i][mm][kk][last]; // momoization 
     int ans = 0; 
     ans += dp(i+1,last==1?mm+1:1,kk+(last!=1?1:0),1); // choose black as a color of this one and update state (mm, kk) 
     ans += dp(i+1,last==0?mm+1:1,kk+(last!=0?1:0),0); // choose white as a color of this one and update state (mm, kk) 
     return memo[i][mm][kk][last] = ans; 
    } 

    public static void main (String[] args) throws java.lang.Exception { 
     n = 4; m = 3; k = 1; 
     memo = new int[n+1][m+1][k+1][2]; 
     for(int i=0;i<n;i++) for(int j=0;j<=m;j++) for(int l=0;l<=k;l++) Arrays.fill(memo[i][j][l], -1); 
     System.out.print(dp(1,1,0,1)); 
    } 

Answer 2

Es gibt eine ganz einfache Rekursion, wenn T (N, M, K) ist die Ausgabe:

T(N, M, K) = T(N - 1, M, K - 1) + T(N - 2, M, K - 1) + ... + T(N - M, M, K - 1) 

Ein gültiger Barcode (N, M, K) ist immer ein kleiner gültiger Barcode plus eine neue Farbe, die Größe dieser neuen Farbe könnte alles von 1 bis M sein.

Dank dieser Beziehung können Sie für jedes M eine N x K Tabelle erstellen und das Problem in O (N M K) mit dynamischer Programmierung lösen .

Diese Regeln sollten ausreichen, um die Wiederholung zu initialisieren:

T(N, M, K) = 0 if (K >= N) and 1 if (K = N - 1) 
T(N, M, K) = 0 if ((K+1) * M < N)