2020-12-01から1ヶ月間の記事一覧

全探索、動的計画法、分枝限定法(枝刈り)、ダイクストラを実装して比較してみた

はじめに 『アルゴリズムパズル ―プログラマのための数学パズル入門』という本を読んでいたところ、問題20の山下りの最大和が以下のようなものだった。 正の整数が三角形状に配置されている。この三角形の頂点から初めて、それぞれの回想で直前に選んだ数字…