グリッド・多次元表の局所DP
グリッド経路や多次元表の依存関係をDAG順に並べ、隣接する小さな状態集合から各セル・各添字を更新する。
この典型を扱う単元: グリッド・多次元表の局所DPを設計する
検索別名: grid DP、table DP、グリッドDP、二次元DP
未知問からこの典型を見つける手掛かり
- 扱う対象
- DAG
- グリッド
- セル
- 列
- 行
- 表
- 使う手掛かり
- 上と左
- 単調経路
- 小さい添字から
- 行ごとに
- 近傍状態
- 保つ不変量
- DAG順
- 依存先を計算済み
- 境界の番兵
- 局所遷移
- 求めるもの
- 場合の数
- 多次元状態の値
- 最大正方形
- 経路の最適値
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: DP状態と遷移
関連する典型
学習成果と学習単位
グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。
グリッド・多次元表の局所DPを設計するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC221 H「Count Multiset」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC227 F「Treasure Hunting」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC259 Ex「Yet Another Path Counting」 公式問題主題: 平方根・閾値による軽重分類 / 補助タグ
- ABC311 E「Defect-free Squares」 公式問題主題: グリッド・多次元表の局所DPを設計する / 主タグ
- ABC347 F「Non-overlapping Squares」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC358 G「AtCoder Tour」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC415 E「Hungry Takahashi」 公式問題主題: グリッド・多次元表の局所DPを設計する / 主タグ
- ABC443 E「Climbing Silver」 公式問題主題: グリッド・多次元表の局所DPを設計する / 主タグ
- ABC464 E「Fill-Rect Query」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ