# Introduction

Typically a DP problem involves searching for a sequence of decisions that arrives at a maximum or minimum value. Let's define:

t = 1...N

A "stage" of the problem. When t=N, we have reached the end of the problem. This is usually the variable representing time / planning horizon, but not necessarily

s_t\in S

State at stage t; S is the space of all possible states

a_t\in A

Action at stage t; A is the space of all possible actions

r_t(s_t, a_t)

Reward function if we take action a_t at state s_t

R(s_N)

Reward if we end on state s_N. This is the cost/reward of our base case, a subproblem that we can immediately solve without recursion. If we reach s_N, we have no possible actions.

Now the optimality equation / value function / objective recurrence is:

v_t(s_t) = \left.\underset{a_t\in A}{\max/\min}\,\middle\{v_{t+1}(s_{t+1}) + r_t(s_t, a_t) \right\}

For a rod of length N,

\text{CutRod}(n)  = \begin{cases}
    0       &   \text{if } n = 0\\
    p_1     &   \text{if }n = 1\\
    \displaystyle\max_{1\leqslant i\leqslant n}\{
    \text{CutRod}(n-i) + p_i
    \}  &   \text{otherwise}
\end{cases}

In this case, the remaining length of the rod is the state s_t, and the number of units of rod to cut is the action a_t. We immediately encounter the first exception of the definition of stage t. The only thing that's constant is the initial length of the rod, or the maximum length we can cut in 1 go. Therefore the stage is technically time, but it ranges from 1...N since the max number of cuts we can make is just the total length N (just cut 1 unit at a time).

The rest of the variables are straightforward to find: the revenue of a cut is the reward function; final reward is either 0 or p_1, and s_{n+1} is the new length after the cut.

Let's list each component:

t = 1...N

Stage is the "time" elapsed or the total number of cuts we have made

s_t\in S

State is the length of the remaining rod

a_t\in A

Action the the possible cuts we can make. Ranges from 1 to s_t

r_t(s_t, a_t)

Reward is the revenue of the cut

R(s_N)

Base cases, s_N = 0 or s_N = 1 which means R(0) = 0, R(1) = p_1

optimality equation is:

\max_{1\leqslant i\leqslant n}\{\text{CutRod}(n-i) + p_i\}

For strings A[1...n], B[1...m]

{\text{EditDist}(i, j)} = \begin{cases}
i & \text{if } j = 0\\j & \text{if } i = 0\\
\min \left.\begin{cases}

\text{EditDist}(i, j-1) + 1\\
\text{EditDist}(i-1, j) + 1\\
\text{EditDist}(i-1, j-1) + \begin{cases}1 & \text{if }A[i]\ne B[j]\\
0 & \text{if }A[i]= B[j]
\end{cases}\\

\end{cases}\right\} & \text{Otherwise}
\end{cases}