My previous approach of trying to associate x[i] directly with x[i-1] has problem, mainly the handling of multiple insertion/deletions. This approach violates one pricinple of inductions => it was attacking too many steps at a time.

But previous discussion still yields valuable insights, but this time, we will do it 1 step at a time.

so consider position x[i], which ONE step can we do here?

  1. Delete x[i] for tail from 0 to 255 Cost(i, tail) = min(cost, D + cost(i -1, tail))

  2. Insert a value to the right. Note we dont consider insertion to the left, because that is covered in the previous step

  3. Update current value to a new value

Note that after2, we can keep inserting, thus we actually have 2 states

  1. a smooth array with last element drived from i, delete or update

  2. a smooth array ending with a value, this array is created with 1, and a number of inserting

So at each step, we first apply 1), and then apply 2)

action(i) populateTailed populateInsertion cost(i, v) = min(costTail(i, v), costInsert(i, v))

populateTailed for v from 0 to 255 costTail(i, v) = min(costTail(i,v), D + cost(i -1, v)) //deletion case

for tailV from 0 to 255 for prevV from (tailV - M, tailV + M) costTail(i, tailV) = min(costTail(i, v), abs(tailV - x[i]) + cost(i-1, tailV))

populateInsertion for v from 0 to 255 for tailV from 0 to 255 costInsert(i, v) = min(costInsert(i,v), InsertionCost(tailV, v) + costTail(i, tailV))

Note you can reverse the direction of your sub problem as well, i.e., the subproblem becomes cost(i, v)