動的計画法
2024/11/1 4:54:00
あれ
2026/1/24 1:41:00
累積和も DP も、しゃくとり法も、要約空間に写像して意味を圧縮する計算に見えるようになった
— naoya (@naoya_ito) January 23, 2026
そしてたぶんこの見方は他のアルゴリズムやデータ構造にも適用できる
「計算を速くするとは、操作を減らすことではなく、適切な要約空間に写像して意味を圧縮すること」と見れそうな気がする
https://x.com/naoya_ito/status/2014560007514423326
DP は部分問題の解のreduceで定式化されるので、累積和と同じ構造ですね
— Kenta Murata (@KentaMurata) January 23, 2026
『木DPから学ぶ、動的計画法の構造と双対性』
2026/1/24 1:39:00