マツシタのお勉強

メモ化再帰

ナップザンク問題

dp(i, j)を以下のように定義する。 dp(i, j) := i番目の荷物を重さj以下のなるように操作した時(その荷物を入れるか否か)の最大の価値 深さ優先で、その荷物を入れる場合と入れない場合とを比べ、価値がより大きくなるものを選択していく。

AtCoder ABC D: 経路

問題 D: 経路 - AtCoder Beginner Contest 037 | AtCoder 解法 以下をポイントにして動的計画法により解く。 求めたいもの: 経路数 マスを進む度に変わるもの: (i, j) 現在いるマスがi行j列のマス 進めるマスが無くなったらを抜ける条件にして再帰関数で実装…

トポロジカルソートの組合せを数え上げる

問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder 与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると1つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満…

最短経路DAGを作って経路の数え上げをする(動的計画法)

問題 C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder ソースコード一部 ソースコードの全体は最後に添付。 解説 今回の問題では、スタートからゴールまでの最短経路が複数存在し、その経路数を求める問題である。 よって、初めに行うことは…

食費を節約するために動的計画法を用いる

問題 C: 節制 - AtCoder Beginner Contest 013 | AtCoder はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。 普通の食事: A 円の出費をして、満腹度が B 増える。 質素な食事: C 円の…

フィボナッチ数列を例にして動的計画法を学ぶ

動的計画法とは Wiki 下記2条件を満たすアルゴリズム 1. 部分問題を解き、その結果を利用して、全体問題を解く 2. 部分問題の計算結果を再利用する らしいです。 動的計画法 - Wikipedia フィボナッチ数列を例にする フィボナッチ数列が良く動的計画法を説…