Rappresenta il numero naturale come somma di quadrati utilizzando la programmazione dinamica

Question

Il problema è trovare il numero minimo di quadrati necessari per sommare un numero n.

Alcuni esempi:

min[ 1] = 1 (1²) 
min[ 2] = 2 (1² + 1²) 
min[ 4] = 1 (2²) 
min[13] = 2 (3² + 2²) 

Sono consapevole di Lagrange's four-square theorem in cui si afferma che ogni numero naturale può essere rappresentato come la somma di quattro quadrati.

Sto cercando di risolvere questo utilizzando DP.

Questo è quello che mi è venuta (la sua non correggere)

min[i] = 1 where i is a square number 
min[i] = min(min[i - 1] + 1, 1 + min[i - prev]) where prev is a square number < i 

Qual è il modo DP corretto per risolvere questo problema?

Answer 1

io non sono sicuro se DP è il modo più efficace per risolvere questo problema, ma hai chiesto DP.

min [i] = min (min [i - 1] + 1, 1 + min [i - prev]) dove prev è un numero quadrato < i
Questa è vicino, avrei scritto condizione come

min[i] = min(1 + min[i - prev]) for each square number 'prev <= i' 

nota, che per ogni i è necessario controllare diversi valori possibili di prev.

Ecco la semplice implementazione in Java.

Arrays.fill(min, Integer.MAX_VALUE); 
min[0] = 0; 
for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j*j <= i; ++j) { 
     min[i] = Math.min(min[i], min[i - j*j] + 1); 
    } 
} 

Answer 2

mi sembra che sei vicino ...

Stai prendendo il min() di due termini, ognuno dei quali è min[i - p] + 1, dove p è 1 o qualche altra piazza < i.

Per risolvere questo problema, basta prendere il min() di min[i - p] + 1 sopra tutti p (dove p è un quadrato < i).

Questo sarebbe a modo corretto. Potrebbe esserci un modo più veloce.

Inoltre, potrebbe facilitare la leggibilità se si danno nomi min[] e min() diversi. :-)

P.S. l'approccio di cui sopra richiede che si memoize min[], esplicitamente o come parte del framework DP. Altrimenti, la complessità dell'algoritmo, dovuto alla ricorsione, sarebbe qualcosa come O (sqrt (n)!): -p anche se il caso medio potrebbe essere molto meglio.

P.P.S. Vedi @ Risposta di Nikita per una buona implementazione. A cui aggiungerei le seguenti ottimizzazioni ... (Non sto snellando la sua implementazione - lo ha presentato come semplice.)

1. Verificare se n è un quadrato perfetto, prima di entrare nel ciclo esterno: se è così, min [n] = 1 e abbiamo finito.
2. Verificare se è un quadrato perfetto prima di entrare nel ciclo interno: in tal caso, min [i] = 1 e saltare il ciclo interno.
3. Break out del loop interno se min [i] è stato impostato su 2, perché non migliorerà (se fosse possibile farlo con un quadrato, non avremmo mai inserito il ciclo interno, grazie al precedente ottimizzazione).
4. Mi chiedo se la condizione di terminazione sul loop interno possa essere modificata per ridurre il numero di iterazioni, ad es. j*j*2 <= i o anche j*j*4 <= i. Penso di sì ma non ho la testa completamente intorno.

5. Per i grandi, sarebbe più veloce calcolare un limite per j prima del ciclo interno e confrontare j direttamente con esso per la condizione di terminazione del loop, piuttosto che squadrare j su ogni iterazione del ciclo interno. Per esempio.

   float sqrti = Math.sqrt(i); 
   for (int j = 1; j <= sqrti; ++j) { 
   

   D'altra parte, è necessario j^2 per il passo di ricorsione in ogni caso, così finché si memorizza, si potrebbe anche usarlo.

Answer 3

Per varietà, ecco un'altra risposta:

Definire minsq [i, j] come il numero minimo di caselle da {1^2, 2^2, ..., j^2} che riassumere a i. Poi la ricorsione è:

minsq[i, j] = min(minsq[i - j*j, j] + 1, minsq[i, j - 1]) 

cioè, per calcolare minsq [i, j] ci sia per uso j^2 o noi non lo fanno. La nostra risposta per n è allora:

minsq[n, floor(sqrt(n))] 

Questa risposta è forse concettualmente più semplice di quello presentato in precedenza, ma il codice-saggio è più difficile in quanto si ha la necessità di stare attenti con i casi di base. La complessità temporale per entrambe le risposte è asintoticamente la stessa.

Answer 4

Presento un algoritmo di programmazione dinamica molto efficiente per trovare il numero minimo di interi positivi di potenza dati per raggiungere un determinato target in JavaScript.

Ad esempio per raggiungere 50000 con numeri interi di 4a potenza il risultato sarebbe [10,10,10,10,10] o per raggiungere 18571 con numeri interi di 7a potenza risulterebbe [3,4]. Questo algoritmo sarebbe nemmeno lavorare con potenze razionali, come per raggiungere 222 con numeri interi di/^° potere sarebbe [ 32, 32, 243, 243, 243, 3125 ]

function getMinimumCubes(tgt,p){ 
 
    var maxi = Math.floor(Math.fround(Math.pow(tgt,1/p))), 
 
     hash = {0:[]}, 
 
     pow = 0, 
 
     t = 0; 
 
    for (var i = 1; i <= maxi; i++){ 
 
    pow = Math.fround(Math.pow(i,p)); 
 
    for (var j = 0; j <= tgt - pow; j++){ 
 
     t = j + pow; 
 
     hash[t] = hash[t] ? hash[t].length <= hash[j].length ? hash[t] 
 
                  : hash[j].concat(i) 
 
         : hash[j].concat(i); 
 
    } 
 
    } 
 
    return hash[tgt]; 
 
} 
 

 
var target = 729, 
 
    result = []; 
 
console.time("Done in"); 
 
result = getMinimumCubes(target,2); 
 
console.timeEnd("Done in"); 
 
console.log("Minimum number of integers to square and add to reach", target, "is", result.length, "as", JSON.stringify(result)); 
 

 
console.time("Done in"); 
 
result = getMinimumCubes(target,6); 
 
console.timeEnd("Done in"); 
 
console.log("Minimum number of integers to take 6th power and add to reach", target, "is", result.length, "as", JSON.stringify(result)); 
 

 
target = 500; 
 
console.time("Done in"); 
 
result = getMinimumCubes(target,3); 
 
console.timeEnd("Done in"); 
 
console.log("Minimum number of integers to cube and add to reach", target, "is", result.length, "as", JSON.stringify(result)); 
 

 
target = 2017; 
 
console.time("Done in"); 
 
result = getMinimumCubes(target,4); 
 
console.timeEnd("Done in"); 
 
console.log("Minimum number of integers to take 4th power and add to reach", target, "is", result.length, "as", JSON.stringify(result)); 
 

 
target = 99; 
 
console.time("Done in"); 
 
result = getMinimumCubes(target,2/3); 
 
console.timeEnd("Done in"); 
 
console.log("Minimum number of integers to take 2/3th power and add to reach", target, "are", result);