配列を正確に k 個のサブセグメントに分割する必要がある場合は、動的計画法で 2 番目のパラメーター (分割するセグメントの数) を追加するだけです。
つまり、次の dp を検討します。
dp[i][j] は、最初の i 個の要素を正確に j 個のセグメントに分割した場合の答えです。
無効な状態に注意してください。
ダイナミクスの再計算は同じですが、2 番目のパラメーターが考慮されます。つまり、dp[i][k] をカウントし、最後のサブセグメント j の左側の境界をソートして、dp[j - 1][k - 1] とセグメントの値を通じて dp[i][k] を再計算します。 [j;i]。