動的計画法
問題 週末yukicoder。ずっと動的計画法の練習です。 解法 おなじみ動的計画法で解きます。一度選んだアトラクションが再度選べるのとその際価値が前回の半分(切り捨て)になるところが、ちょっといつもの問題と違うところですね。 アトラクションの価値が元…
週末yukicoder。 問題 問題はこちら 解法 動的計画法です。 個のお寿司が手前に流れてきたときの美味しさの最大をとします。この時と定義しておきます。 の時はお寿司が1つだけなので、そのお寿司を取るしかないので、 の時について、場合を分けて考えてみ…
個の町々で目的の町を目指して、時間内にもっとも安い値段で辿り着く場合を求める問題です。 問題 問題はこちら 解法 動的計画法で解きます。 ちなみに動的計画法の参考記事では下記の記事がとてもわかりやすいです。 典型的な DP (動的計画法) のパターンを…