Ich bin jetzt nicht der Fachmann in Sachen dynamische Programmierung.
Bei Wikipedia steht:
"Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt"
Ist dies denn hier der Fall?
Ich denke nicht! Denn wenn ich z.B. die Karte in zwei Hälften teile und jede davon optimal aufteile, dann kann ich beim Zusammensetzen immer noch durch die Nahtstelle und den damit verbundenen Punktabzug suboptimal werden. Außerdem könnte es sein, dass ich bei einer der beiden Lösungen gezwungenermaßen eine der beiden Zivilisationen benachteilige. Das könnte ich in der anderen Hälfte wieder ausgleichen. Löse ich jedoch beide getrennt, weiß ich davon garnichts und kann das nicht berücksichtigen.
An den oben genannten O(n²)-Algorithmus glaube ich jedenfalls nicht.
Zumal da "n" die Anzahl der Zeilen sein soll - und die Anzahl der Spalten ist dann völlig irrelevant, was die Komplexität angeht?