Haskellで動的計画法を実装する2つの方法 出典: Easily Solving Dynamic Programming Problems in Haskell by Memoization of Hylomorphisms ザ圏論的やり方としては①Dynamorphism、手続き的な方法として②STモナドが挙げられる。 DynamorphismはHylomorphismをメモ化したようなもので、詳しくはlotz氏のサイトを参照してほしい。 Haskellerとしては、Dynamorphismはとても憧れる手法である。しかし、思ったよりも速度が出ない。。 このスクラップに二通りのLCSの解法を記載したが、いずれもTLEであった。 lotz氏によると、メモ化されたデータ構造にはO(n)でしかアクセスできないことが理由とのこと。 この記事では、STモナドによるメモ化再帰を用いた動的計画問題
![Haskellで動的計画法を攻略する](https://cdn-ak-scissors.b.st-hatena.com/image/square/81151878e1bc4542571bd21a5c04b4d299290d2c/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--aUJKihOl--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3AHaskell%2525E3%252581%2525A7%2525E5%25258B%252595%2525E7%25259A%252584%2525E8%2525A8%252588%2525E7%252594%2525BB%2525E6%2525B3%252595%2525E3%252582%252592%2525E6%252594%2525BB%2525E7%252595%2525A5%2525E3%252581%252599%2525E3%252582%25258B%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3A4tsuzuru%252Cx_203%252Cy_121%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9zdG9yYWdlLmdvb2dsZWFwaXMuY29tL3plbm4tdXNlci11cGxvYWQvYXZhdGFyLzI4OTI2NzkxM2IuanBlZw%3D%3D%252Cr_max%252Cw_90%252Cx_87%252Cy_95%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)