はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける戻すDP問題

戻すDP

  • dp[i+1]からdp[i]を復元することで問題を解くテク
  • 間違ってたらごめんなさいメモ
    • ナップサックDPで順番を変えても問題なくて、一部なくすとかなら戻すDPかも
    • 多項式の母関数がDPになってる問題で使える(遷移が多項式の掛け算なので、多項式で割ることが”戻す”ことになる)参考
  • 参考