DPの話 - aizuzia

この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と

[tinsep19]

最短経路は + と min、最長経路は + と max、確率DPは * と +、経路総数も * と +、DPにまつわる各種演算は分配法則が成り立つことが本質的に重要

[be_a_prgrmr]

読むぞ

[kenichiice]

動的計画法

[ikajigoku]

>DPとは、DAG上の最短経路を求めることです。

[ymiyata3]

DPはすでに理解してるけどこういう風に考えた事はなかったな。面白い

[kabiy]

“DPの話 - aizuzia”