Haskellで動的計画法を攻略する

Haskellで動的計画法を実装する２つの方法 出典： Easily Solving Dynamic Programming Problems in Haskell by Memoization of Hylomorphisms ザ圏論的やり方としては①Dynamorphism、手続き的な方法として②STモナドが挙げられる。 DynamorphismはHylomorphismをメモ化したようなもので、詳しくはlotz氏のサイトを参照してほしい。 Haskellerとしては、Dynamorphismはとても憧れる手法である。しかし、思ったよりも速度が出ない。。 このスクラップに二通りのLCSの解法を記載したが、いずれもTLEであった。 lotz氏によると、メモ化されたデータ構造にはO(n)でしかアクセスできないことが理由とのこと。 この記事では、STモナドによるメモ化再帰を用いた動的計画問題

[shunkeen]

頂点と辺に重みがあるDAGをトポロジカルソート順で畳み込むと、だいたいDPになるけど、畳み込む時に半環が必要になるやーつ。有向辺x→yについて、y = y ⊕ x ⊗ x→y みたいに畳み込むやーつ。

[zyzy]

競プロに便利な奴だ

[programmablekinoko]

しっかりCSしてた

[Nyoho]

トロピカル出てきた