公式解説の記号および説明ををそのまま使います。 公式解説より、DP の漸化式は

\[ \mathrm{DP}[t][k] = \max_{\substack{c_1 + \cdots + c_N = M \\ c_1 \ge \dots \ge c_N}} \dfrac{1}{N} \sum_{i=1}^N \mathrm{DP}[t+1][k+c_i] \]

となります。ここで条件を満たす全ての組 \((c_i)\) を愚直に列挙することを考えます。\(c_i > 0\) となる部分だけに着目すると、条件を満たす \((c_i)\) はまさに、自然数 \(M\) の分割のうち、項数が \(N\) 以下となるようなもの全てです （自然数の分割については https://ja.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B0%E3%81%AE%E5%88%86%E5%89%B2 を参照してください）。

\(M=30\) のとき、（項数が \(N\) 以下という条件を外した）分割の総数は \(p(30) = 5604\) であり、また分割の長さの和は \(54563\) であることが全探索により確かめられます。 よって DP の遷移を \(c_i=0\) の部分はまとめて計算し、それ以外は愚直に遷移したとき、あらかじめ全ての分割 \((c_i)\) を列挙しておくことで、本問題の制約の範囲では高々 \(30 \times 30 \times (5604+54563) = 54150300\) 回の遷移により DP テーブルを全て埋めることができ、多くの言語で十分 AC できます。

参考実装: https://atcoder.jp/contests/abc404/submissions/65498496

なお分割数 \(p(M)\) の漸近公式が知られており、特に \(M\) についていかなる多項式よりも漸近的に高速に発散します（上記 wikipedia 参照）。よってこのアルゴリズムは公式解説より漸近的に遅いです。