The Book

The Art and Theory of Dynamic Programming (Amazon), by Stuart E. Dreyfuse and Averill M. Law.

The Solutions

1.1

Let $S(x, y)$ be the smallest distance from Point $A(0, 0)$ to $(x, y)$, and $a_d(x, y)$/$a_u(x, y)$ be the distance of the arc down/up from $(x, y)$. $S(0, 0) = 0$; Final answer: $min{S(4, j)}$

$S(x, y) = min\{a_d(x - 1, y + 1) + S(x - 1, y + 1), a_u(x - 1, y - 1) + S(x - 1, y - 1)\}.$

1.2

In addition to 1.1, denote $r(x, y)$ as the "bonus value" at $(x, y)$; all $r(x, y) = 0$ except those specified by the problem.

$S(x, y) = min\{a_d(x - 1, y + 1) + S(x - 1, y + 1), a_u(x - 1, y - 1) + S(x - 1, y - 1)\} + r(x, y).$

1.3

Notice the definition of N: Fig 1.3 is actually a N=4 case.

DP requires $2N + (\frac{N(N + 1)}{2} - 2N)*2 = n^2 - n$ additions, and $(\frac{N(N + 1)}{2} - 2N) + N$ comparisons; Brute-force computes $2^N$ paths and thus requires $N \cdot 2^N$ additions and $2^N - 1$ comparisons.