動的計画法の核心パターンと実装テクニック
動的計画法の基本フレームワーク
動的計画法は過去の計算結果を再利用し、重複計算を回避する手法です。計算結果は通常1次元または2次元の配列に格納されます。実装には以下の3ステップが不可欠です。
ステップ1: 状態の定義
配列memo[i]の意味を明確に定義します。例えばmemo[i]が「i段目までの階段を登る方法の総数」を表す場合、最終的にmemo[n]が求める解となります。 ...
8月2日 20:11 投稿
奇想天外なアイデアがコードで現実になる場所
8月2日 20:11 投稿