Programmazione dinamica piramidi

Question

Ho incontrato questa domanda in un'intervista e non riuscivo a capirlo. Credo che abbia una soluzione di programmazione dinamica ma mi sfugge.

Dato un numero di mattoncini, è possibile generare il numero totale di piramidi 2d possibili, in cui una piramide è definita come qualsiasi struttura in cui una fila di mattoni ha meno meno mattoni della fila sottostante. Non devi usare tutti i mattoni.

Un mattone è semplicemente un quadrato, il numero di mattoni di fila è l'unico bit importante di informazioni.

Davvero bloccato con questo, ho pensato che sarebbe stato facile risolvere ogni problema 1 ... n in modo iterativo e somma. Ma inventare il numero di piramidi possibili con esattamente i mattoni mi sta sfuggendo.

esempio, n = 6

X 

XX 

X 
XX XXX 

X 
XXX XXXX 

XX  X 
XXX XXXX XXXXX 

X 
XX  XX  X 
XXX XXXX XXXXX XXXXXX 

Quindi la risposta è 13 possibili piramidi da 6 mattoni.

modificare

sono convinto che questo è un problema di programmazione dinamica, perché ha senso (una volta che hai stabilito la prima riga) basta guardare l'indice nella propria matrice memorizzato del resto dei mattoni per vedere quante piramidi si adattano in cima.

ha anche senso considerare righe inferiori di larghezza almeno n/2 perché non possiamo avere più mattoni cima che sulla riga inferiore TRANNE ed è qui perdo e mente cade a pezzi, in alcuni (pochi casi) puoi N = 10

X 
XX 
XXX 
XXXX 

Ora la fila inferiore ha 4 ma ci sono 6 rimasti da mettere sopra

Ma con n = 11 non possiamo avere una fila inferiore con meno di n/2 mattoni. C'è un'altra strana incongruenza come quella con n = 4 in cui non possiamo avere una riga inferiore di n/2 = 2 mattoni.

Answer 1

Scegliamo una definizione adatta:

f(n, m) = # pyramids out of n bricks with base of size < m 

La risposta che state cercando per ora è (dato che N è il tuo numero di ingresso di mattoni):

f(N, N+1) - 1 

Rompiamo che verso il basso:

• Il primo N è ovvio: questo è il numero di mattoncini.
• La riga inferiore conterrà al massimo N mattoni (perché questo è tutto ciò che hai), quindi N+1 è un limite inferiore sufficiente.
• Infine, lo - 1 è lì perché tecnicamente la piramide vuota è anche una piramide (e verrà quindi conteggiata) ma la escluderai dalle tue soluzioni.

---

I casi di base sono semplici:

f(n, 0) = 1 for any n >= 0 
f(0, m) = 1 for any m >= 0 

In entrambi i casi, è la piramide vuoto che stiamo contando qui.

---

Ora, tutto ciò di cui abbiamo ancora bisogno è una formula ricorsiva per il caso generale.

Supponiamo di ricevere n e m e di scegliere i mattoncini i sul livello inferiore. Cosa possiamo posizionare sopra questo livello? Una piramide più piccola, per la quale abbiamo lasciato i mattoni n - i e la cui base ha la dimensione < i. Questo è esattamente f(n - i, i).

Qual è l'intervallo per i? Possiamo scegliere una riga vuota in modo da i >= 0. Ovviamente, i <= n perché abbiamo solo mattoncini n. Ma anche, i <= m - 1, per definizione di m.

Questo porta alla espressione ricorsiva:

f(n, m) = sum f(n - i, i) for 0 <= i <= min(n, m - 1) 

---

è possibile calcolare in modo ricorsivo f, ma usando la programmazione dinamica sarà più veloce, ovviamente. Memorizzare la matrice dei risultati è semplice, quindi la lascio a voi.

---

Tornando alla domanda principale che f(N, N+1)-1 è la risposta che stai cercando, in realtà non importa quale valore da scegliere per m finché è > N. Sulla base della formula ricorsiva è facile dimostrare che f(N, N + 1) = f(N, N + k) per ogni k >= 1:

f(N, N + k) = sum f(N - i, i) for 0 <= i <= min(N, N + k - 1) 
      = sum f(N - i, i) for 0 <= i <= N 
      = sum f(N - i, i) for 0 <= i <= min(N, N + 1 - 1) 

Answer 2

In quanti modi è possibile creare una piramide di larghezza n? Mettendo qualsiasi piramide di larghezza n-1 o meno ovunque sopra il livello di n mattoni. Quindi se p (n) è il numero di piramidi di larghezza n, quindi p (n) = somma [m = 1 a n-1] (p (m) * c (n, m)) , dove c (n, m) è il numero di modi in cui è possibile inserire uno strato di larghezza di m in cima ad uno strato di larghezza n (ho fiducia che si può lavorare che uno voi stessi).

Questo, tuttavia, non pone una limitazione sul numero di mattoni. In genere, in DP, qualsiasi limitazione delle risorse deve essere modellata come dimensione separata. Quindi il tuo problema è ora p (n, b): "Quante piramidi puoi costruire di larghezza n con un totale di b mattoni"? Nella formula ricorsiva, per ogni possibile modo di costruire una piramide più piccola sopra quella corrente, è necessario fare riferimento alla quantità corretta di mattoni rimanenti. Lascio che sia una sfida per te elaborare la formula ricorsiva; fammi sapere se hai bisogno di qualche suggerimento.

Answer 3

Puoi pensare alla tua ricorsione come: dato x mattoni a sinistra dove hai usato i mattoncini n nell'ultima fila, quante piramidi puoi costruire. Ora puoi riempire le righe dalla riga superiore a quella inferiore o dalla riga inferiore a quella superiore. Spiegherò il primo caso.
Qui la ricorsione potrebbe essere simile a questa (left è il numero di mattoni a sinistra e last è il numero di mattoni utilizzato su ultima riga)

f(left,last)=sum (1+f(left-i,i)) for i in range [last+1,left] inclusive. 

Da quando si utilizza i mattoni sulla riga corrente avrete left-i mattoni sinistra e i sarà il numero di mattoni usati su questa riga.

Codice:

int calc(int left, int last) { 
    int total=0; 
    if(left<=0) return 0; // terminal case, no pyramid with no brick 
    for(int i=last+1; i<=left; i++) { 
     total+=1+calc(left-i,i); 
    } 
    return total; 
} 

Lascio a voi per implementare memoized o bottom-up dp versione. Inoltre, potresti voler iniziare dalla riga inferiore e riempire le righe superiori nella piramide.

Answer 4

Dal momento ci viene chiesto di contare piramidi di qualsiasi cardinalità inferiore o uguale a n, possiamo considerare ogni cardinalità a loro volta (piramidi di 1 elemento, 2 elementi, 3 ... ecc.) e riassumili. Ma in quanti modi diversi possiamo comporre una piramide dagli elementi k? Lo stesso numero del conteggio delle partizioni distinte di k (ad esempio, per k = 6, possiamo avere (6), (1,5), (2,4), and (1,2,3)). Una funzione/ricorrenza di generazione per il conteggio di partizioni distinte è descritta in Wikipedia e una sequenza su OEIS.

Recurrence, basato sul Pentagonal number Theorem:

q(k) = ak + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22)... 
    where ak is (−1)^(abs(m)) if k = 3*m^2 − m for some integer m and is 0 otherwise. 

(The subtracted coefficients are generalized pentagonal numbers.) 

Poiché la ricorrenza descritto in Wikipedia obbliga il calcolo di tutti i precedenti q(n) 's per arrivare a una maggiore q(n), possiamo semplicemente sommare i risultati lungo la strada per ottenere il nostro risultato

codice

JavaScript:

function numPyramids(n){ 

    var distinctPartitions = [1,1], 
     pentagonals = {}, 
     m = _m = 1, 
     pentagonal_m = 2, 
     result = 1; 

    while (pentagonal_m/2 <= n){ 
    pentagonals[pentagonal_m] = Math.abs(_m); 
    m++; 
    _m = m % 2 == 0 ? -m/2 : Math.ceil(m/2); 
    pentagonal_m = _m * (3 * _m - 1); 
    } 

    for (var k=2; k<=n; k++){ 
    distinctPartitions[k] = pentagonals[k] ? Math.pow(-1,pentagonals[k]) : 0; 
    var cs = [1,1,-1,-1], 
     c = 0; 
    for (var i in pentagonals){ 
     if (i/2 > k) 
     break; 
     distinctPartitions[k] += cs[c]*distinctPartitions[k - i/2]; 
     c = c == 3 ? 0 : c + 1; 
    } 
    result += distinctPartitions[k]; 
    } 
    return result; 
} 

console.log(numPyramids(6)); // 13