Hi Larry,

Thanks for considering using this problem! Let me briefly explain the solution below:

The sequence is fixed once the first K elements are chosen. Once the first K elements are chosen so that their sum is S, the entire array is smooth. So we only need to decide if we want to change each of the first K elements.

We use DP with a state of [i][curSum][hasPlaceholder] of size [5000][5000][2]. The DP value stores the minimum number of changes to achieve that.

i: We have considered the first i elements. i <= K
sum: The first i elements have a sum of curSum
hasPlaceholder: We have reserved one element for a later change, which can be set to anything later. As long as we have one reserved element and curSum does not exceed S, we can always achieve a smooth array. Because after K elements if curSum <= S, we can just let this element be S - curSum.

In the DP, for each of the first K element, we decide:
1) If we should change it. Note that elements i, i+K, i+2K, ... must be the same. We can only choose not to change when they are already the same.
2) If we choose to change, to what value we should change it to. Here we shall not enumerate all new values from 0 to S, which would be too slow. We can optimize here by only considering the values A[i], A[i+K], A[i+2K]... (because only by changing to these values we can save a few operations). We also consider changing elements i, i+K, i+2K... all to "placeholder".

The entire DP runs in about O(K*N/K*S)=O(NS) time.
K: we have K elements to consider.
N/K: for each element (or say element group), if we change it, there are N/K candidates (aka, A[i], A[i+K], A[i+2K]... plus placeholder)
S: we need to enumerate curSum from the previous states

Hope this helps! Let me know if anything is unclear.

Best,
Bowen