まず、動的計画法の実現方法にはトップダウン方式とボトムアップ方式があり、メモ化再帰はトップダウン方式の実現方法に当たります
こちらは日本語版のWikipediaにも記載があります
https://ja.m.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95
トポロジカルソートの知識が必須になるのは、ボトムアップ方式で実現する場合です
メモ化再帰する場合にはトポロジカルソートを意識する必要はありません
ここで行われているメモ化再帰の実装は、深さ優先検索を用いたトポロジカルソートの実装と類似しており、結果的にトポロジカルソートの逆順で計算結果が確定されていくことになります
データ構造,アルゴリズム,デザインパターン総合スレ 4
2021/10/12(火) 00:41:32.76ID:mo6bbxTQ
レスを投稿する
ニュース
- 東京都「都民の税金1.5兆円が国に奪われている」「全国に分配されている」に地方民ブチギレ [Hitzeschleier★]
- 高市首相の答弁書に「台湾有事答えない」と明記 存立危機発言当時 [蚤の市★]
- 「もうキモくてキモくて…」29歳女性が語る“おぢアタック”の実態。「俺ならイケるかも」年下女性を狙う勘違い中年男性に共通点が★4 [Hitzeschleier★]
- 自民・麻生太郎副総裁 石破政権の1年は「どよーん」 高市政権発足で「何となく明るくなった」「世の中のことが決まり動いている」★2 [Hitzeschleier★]
- 1人3千円の食品高騰対策、何に使える? あいまいなまま衆院通過 [蚤の市★]
- 【おこめ券】鈴木憲和農相 小泉前農相の備蓄米放出を“反省”「備蓄の円滑な運営を図ってまいります」 [Hitzeschleier★]
