Mi sono imbattuto in questo problema,
There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same. Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will output the number of such sequences using all these numbers. Output your answer modulo 1000000007 (10^9 + 7).
Non riesco a capire la soluzione di questo. Sarà fatto con DP o qualche tipo di DFS con backtracking?
Se sono corretto, la soluzione di attraversamento del grafico è piuttosto semplice: puoi attraversare il grafico con la funzione ricorsiva memorizzando solo i simboli "di sinistra" e l'ultimo usato.
f di input (coppie chiave-valore, dove le chiavi sono 1 .. 4 ; i valori sono n1 .. n4 ) e p - ultimo numero utilizzato e p inizialmente non definito input[i] > 0 e i != p , dove i è una chiave
inputUpd := input (copia per chiamata ricorsiva) inputUpd[i] , perché abbiamo appena usato il simbolo i e ce n'è uno in meno di sinistra p := i , perché abbiamo appena utilizzato i
f(inputUpd, p) (chiamata ricorsiva con input "minore" e ultimo simbolo usato) per ottenere Non ho potuto aiutare me stesso, quindi ecco il codice in JS. Saltalo se vuoi capire da solo la soluzione.
function f(input, prev) {
var acc = 0;
for (i in input) {
if (i != prev && input[i] > 0) {
var inputUpd = {};
for (j in input) {
inputUpd[j] = (j == i) ? (input[j] - 1) : input[j];
}
acc += 1 + f(inputUpd, i);
}
}
return acc;
}
f({'1': 1, '2': 1}) // -> 4: [1], [2], [1,2], [2,1]
f({'1': 1, '2': 2}) // -> 5: [1], [2], [1,2], [2,1], [2,1,2]
f({'1': 1, '2': 3}) // -> 5: same as before, but single '2' is leftover
f({'1': 1, '2': 1, '3': 2, '4': 2}) // -> 288
Leggi altre domande sui tag graph graph-traversal dynamic-programming combinatorics sequence