E' un esercizio di programmazione dinamica.
Riesci a risolvere con la programmazione dinamica il seguente problema:

vengono assegnati 3k punti sulla retta dei reali, ed entro questo multinsieme di punti (lo chiamiamo multinsieme in quanto dei punti possono anche sovrapporsi) ci e' chiesto di individuare k coppie disgiunte dove sia minima la somma sulle varie coppie scelte della distanza tra i due punti membri della coppia.

Abbiamo gia' osservato la seguente proprieta' strutturale di ogni soluzione ottima:

   se (a,b) e' una coppia di punti in una soluzione ottima allora nell'input non vi era alcun punto c con a < c < b.

Questa dovrebbe aiutare non poco ...

Ora, se ancora fai fatica a vedere una soluzione di programmazione dinamica, prova prima a dare (e codificala!) un'elegante soluzione ricorsiva. Cerca poi di contenere l'interfaccia della procedura ricorsiva, facendo solo riferimento ad una variabile globale dove e' contenuta l'istanza globale del problema, in forma gia' riordinata.