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

shunkeen のブックマーク 2023/02/11 22:17

<blockquote class="hatena-bookmark-comment"><a class="comment-info" href="https://b.hatena.ne.jp/entry/4732206439424254436/comment/shunkeen" data-user-id="shunkeen" data-entry-url="https://b.hatena.ne.jp/entry/s/zenn.dev/osushi0x/articles/198bce676e2841" data-original-href="https://zenn.dev/osushi0x/articles/198bce676e2841" data-entry-favicon="https://cdn-ak2.favicon.st-hatena.com/64?url=https%3A%2F%2Fzenn.dev%2Fosushi0x%2Farticles%2F198bce676e2841" data-user-icon="/users/shunkeen/profile.png">Haskellで動的計画法を攻略する</a><ul class="comment-tag" style="list-style: none; margin: 0px;"><li style="float: left">[<a href="https://b.hatena.ne.jp/q/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0">プログラミング</a>]</li><li style="float: left">[<a href="https://b.hatena.ne.jp/q/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95">動的計画法</a>]</li></ul><br><p style="clear: left">頂点と辺に重みがあるDAGをトポロジカルソート順で畳み込むと、だいたいDPになるけど、畳み込む時に半環が必要になるやーつ。有向辺x→yについて、y = y ⊕ x ⊗ x→y みたいに畳み込むやーつ。</p><a class="datetime" href="https://b.hatena.ne.jp/shunkeen/20230211#bookmark-4732206439424254436"><span class="datetime-body">2023/02/11 22:17</span></a></blockquote><script src="https://b.st-hatena.com/js/comment-widget.js" charset="utf-8" async></script>

このブックマークにはスターがありません。
最初のスターをつけてみよう！

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

zenn.dev/osushi0x2023/02/11

Haskellで動的計画法を実装する２つの方法出典： Easily Solving Dynamic Programming Probl ems in Haskell by Memoization of Hylomorphisms ザ圏論的やり方としては①Dynamorphism、手続き的な方法として②STモ...

36 人がブックマーク・4 件のコメント

他のコメントを読む

＼コメントがサクサク読めるアプリです／

はてなブックマーク

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

はてなブックマーク

公式Twitter

はてなのサービス