Ich versuche, bei DP besser zu werden und habe einige Übungsprobleme durchgemacht. Bitte werfen Sie einen Blick auf this one. Ich kann kaum eine Lösung dafür finden, aber es ist nur in Kleinigkeiten. Ich bin nicht in der Lage, sie miteinander zu verbinden und einen richtigen Algorithmus zu entwickeln. Wie würde man das durch dynamische Programmierung effizient lösen? P.S. Dies ist nicht Teil eines laufenden Wettbewerbs oder irgendeiner Art von Auftrag. Es ist nur ein Übungsproblem aus einem vergangenen Wettbewerb.Kann jemand eine dynamische Programmierlösung vorschlagen, um das zu lösen?
Kurze Beschreibung des Problems:
Sie sind gegeben 'n' Anzahl der Scheiben von Höhe und Radius variiert. Sie müssen den größtmöglichen Turm bauen, indem Sie diese Scheiben so verwenden, dass für jede dieser Scheiben sowohl der Radius als auch die Höhe kleiner sind als der Radius und die Höhe der darunter liegenden Scheibe.
Was ich versucht:
ich ein Array dp haben [1 .... n], wobei dp [i] (1 < = i < = n) speichert die Höhe des höchsten Turms können Sie baue nur mit den Discs im Bereich 1 .... i. Dann gibt es für die Disk i + 1 zwei Möglichkeiten. Ich benutze es entweder oder nicht. Also iteriere ich von 1 bis i und füge die Höhen aller Discs hinzu, deren Abmessungen nicht mit der Disc i + 1 in Konflikt stehen. Dann wähle ich das Größere aus dieser Summe + Höhe von Scheibe i + 1 und dp [i] und speichere es in dp [i + 1]. Offensichtlich funktioniert das in einigen Fällen nicht. Ich überprüfe nicht, ob irgendwelche der anderen Discs, die ich ausgewählt habe, sich untereinander widersprechen. Nicht sicher, ob es verständlich ist, aber das ist das Beste, was ich erklären kann.
Bitte definieren Sie das Problem kurz, abgesehen von dem Link. Gib auch an, was du versucht hast. – sashas
Aktualisiert die Frage. –