Je hebt een rij van \(n\) steden \(s_0, \dotsc, s_{n - 1}\) en twee personen die deze steden moeten bezoeken. Als een persoon een stad \(s_i\) bezoekt, mag die achteraf wel geen stad \(s_j\) met \(j \leq i\) meer bezoeken. Voor \(n = 6\) zou het dus in orde zijn als persoon A zijn deel van de steden in volgorde \(s_0, s_2, s_4, s_5\) bezoekt en persoon B de andere steden in de volgorde \(s_1, s_3\), maar het zou niet in orde zijn als A de steden in volgorde \(s_2, s_0, s_4, s_5\) zou bezoeken. Voor elk paar \((s_i, s_j)\) van steden met \(i < j\) heb je de afstand \(d(s_i, s_j) > 0\). De taak is nu als volgt: persoon A vertrekt in \(s_0\) en persoon B vertrekt in \(s_1\). Gezocht is een partitie van de steden zodat als A en B hun steden in volgorde bezoeken de som van de afstanden minimaal is.

Implementeer de interface StedenBezoeken¹ in een klasse genaamd DynamischStedenBezoeken. Schrijf een methode public double bezoek(Steden steden) die de minimale som van de afstanden berekent. De methode steden.aantal() geeft het aantal steden \(n\), en steden.afstand(i, j) geeft de afstand \(d(s_i, s_j)\), zoals beschreven in de interface Steden².

Gebruik eventueel de testklasse SimpleTest³ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.

Tip: denk er eerst over na welke informatie over deeloplossingen voor de steden \(s_0, \dotsc, s_{k−1}\) je nodig hebt om te kunnen beslissen wie het best \(s_k\) bezoekt. Misschien voldoet een voor de hand liggende 1-dimensionale tabel niet, maar is een 2-dimensionale tabel wel nuttig.