### Problem Restated

The problem is to find the minimum of the cost defined by,

$$\sum_{k=0}^3 x_k^2 + u_k^2$$
with the initial condition $x_0=5$ and relation $0\le x_{k+1}=x_k+u_k\le5$. <!-- all variable are integers. -->


### Simple Arithmetic ###

$$
x_0=5\ \stackrel{u_0=-3}{\xrightarrow{\hspace{2em}}}\  
x_1=2\ \stackrel{u_1=-1}{\xrightarrow{\hspace{2em}}}\ 
x_2=1\ \stackrel{u_2=-1}{\xrightarrow{\hspace{2em}}}\ 
x_3=0\ \stackrel{u_3=0}{\xrightarrow{\hspace{2em}}}
$$


The cost of the state transition above is 

$$(5^2+(-3)^2) + (2^2+(-1)^2)+ (1^2+(-1)^2) + (0^2+0^2)=5^2+16=41$$

------

Here is the simple arithmetic that shows 41 is the minimum cost. Note that a square number is always non-negative.

1. If $x_1=0,1,4,5$, then $u_0=-5, -4, -1, 0$. $$\ \sum_{k=0}^3 x_k^2 + u_k^2\ge x_0^2+(u_0^2+x_1^2)\ge 5^2 + 17$$
4. If $x_1=3, x_1=2$, then $u_0=-2, -3$. $$\ \sum_{k=0}^3 x_k^2 + u_k^2= 5^2 + 4 + 9 + (u_1^2+x_2^2 + u_2^2 + x_3^2+u_3^2)\\=5^2 + 13 + (u_1^2+x_2^2 + u_2^2 + x_3^2)\ge 5^2 + 13 + 3=5^2+16,$$ where the last inequality holds as among the numbers $u_1, x_2, u_2$, either all of them are $1$ or $-1$, or one of them is bigger than $1$ or smaller than $-1$, i.e., a number whose square is no less than $2^2=4$. $\checkmark$

Tracing the proof above, we can see that the optimal control sequence is $u_0^*=-3$, $u_1^*=-1$, $u_2^*=-1$, $u_3^*=0$.

### Brute-Force Programming

As Yuval observed, it is a short programming exercise to brute-force the $6^4=1296$ possible feasible solutions. For example, here it is in Python.

```python
min_cost = 999999999999999999  # a number too big
x0 = 5
for x1 in range(6):
    cost0 = x0 ** 2 + (x1 - x0) ** 2
    for x2 in range(6):
        cost1 = cost0 + x1 ** 2 + (x2 - x1) ** 2
        for x3 in range(6):
            cost2 = cost1 + x2 ** 2 + (x3 - x2) ** 2
            for x4 in range(6):
                cost3 = cost2 + x3 ** 2 + (x4 - x3) ** 2
                if min_cost > cost3:
                    min_cost = cost3
print(min_cost)  # 41

# or an expanded one-liner.
min_cost = min(
    sum(x[k] ** 2 + (x[k + 1] - x[k]) ** 2
        for k in range(4))
    for x in product([5], range(6), range(6), range(6), range(6)))
print(min_cost)  # 41 again
```

### Dynamic Programming

To use dynamic programming, we need to find many overlapping problems, with optimal structure that will lead to recurrent relations. Here we have the natural general problems in the form of the following. 
 

How can we compute the function of minimum cost below?
$$f(s, t, x_0)=\min_{0\le x_{k+1}=x_k+u_k\le s\text{ for all }k}\sum_{k=0}^t x_k^2 + u_k^2$$
where all variables are integers. $s\ge0$ and $t\ge0$.

The original problem is the case when $s$ = 5, $x_0=5$ and $t=3$.

<!-- The most critic step in dynamic programming is finding the recurrence relation. --> Once $x_1$ is chosen, the cost for the remaining state transitions is none other than the cost of $t$ state transitions starting from $x_1$. That is,

$$f(s, t, x_0)
=\min_{0\le x_1\le s}\ \left((x_0^2 + (x_1-x_0)^2) + f(s, t-1, x_1)\right)$$

The above recurrent relation enables us to use a nested loop to compute $f$, assume all $x_i\le s$ for some fixed limit $s$.
1. For $t=0$, $f(s, t, x)=x^2$ for all $x$
2. Suppose for some $t$, we have computed $f(s, t-1, x)$ for all $x$. Use the above recurrence relation to computed $f(s, t, x)$ for all $x$.