https://kaage.hatenablog.com/entry/2020/06/20/164506

解説

たとえば、 $dp\left[i\right]\left[j\right]\left[k\right]$ を $i$ 日目に、前日店 $j$ で買い物をし、そこでは $k$ 日連続で買い物をしている、という場合の最小の合計金額とすると、 $O(ND)$ で解くことができます。

このように、最終的な最適解が、条件を絞れば途中まででも必ず最適解となる場合は、最適化問題にDPを採用できる場合が多いです。

今回のような少し複雑なDPもすぐに書き上げられるようになるとよいです。