10になるカードの組み合わせはある？数字の書かれたカードが並んでいる。 この中から好きなカードを選び、書かれた数字の合計が10になる組み合わせは存在するか？ このような「部分和問題」を「動的計画法」を使って効率よく解く方法を考える。 部分和問題を…

どれを持ち帰る？冒険者が旅の途中、たくさんの宝物を見つけました。 しかし、持ち帰れるのは8kgまでです。 持ち帰る宝物の価値が最も高くなるには、どれを持ち帰ればいいのか。 それを知るべく我々はアマゾンの奥地「動的計画法」の奥地へ向かった・・・。 …

全探索では解けないような難しい問題を解くのに欠かせない「動的計画法」について考える。 動的計画法とは 「フィボナッチ数列」の計算 愚直な計算 動的計画法を使う計算 実装 Non-DP DP(メモ化再帰) DP(ループ) →②「ナップサック問題」 動的計画法とは そも…