A puzzle involving dynamic programming, or maybe it doesn't
Here’s a programming challenge:
Evaluate the following recurrence relation efficiently
for a given array
[x0, …, xn−1]
and integer
k.
f ([x0, x1],
k) =
(x0 + x1) / 2
for all k, n = 2.
= 3″>
f ([x0, …,
xn−1],
k) =