We have a chocolate bar of $F\times C$ squares, some of the "chocolate squares" contains almonds. We can only split the chocolate bar by cutting it horizontally or vertically, obtaining two chocolate bars, one of $k\times C$ squares and the other of $F-k\times C$ squares (in case of cutting it horizontally). We want to obtain the minimum number of cuts necessary to split the original bar into several bars with only one type of chocolate squares (with or without almonds).
This problem is sopposed to be solved using dynamic programming, and its driving me a little bit mad. The only recurrence I occur and I think may work is
$$T(i_1,i_2,j_1,j_2)=\min(T(i_1+1,i_2,j_1,j_2)+\gamma_1,T(i_1,i_2-1,j_1,j_2)+\gamma_2,T(i_1,i_2,j_1+1,j_2)+\gamma_3,T(i_1,i_2,j_1,j_2-1)+\gamma_4)$$
Where $T(i_1,i_2,j_1,j_2)$ means the minimum number of cuts necessary to "well-split" the chocolate "sub-bar" wich contains the rows between $i_1$ and $i_2$ and the columns between $j_1$ and $j_2$. Also, $\gamma_l$ is $1+$ the cuts necessary to "well" split the additional row/column of the recurrence if we have to add one cut to the simpler case and $0$ otherwise.
Probably this is not the way to do it, anyway I am also having problems in how to walk the $4$-dimensional matrix induced by my recurrence.
Any idea?
Best Answer
If $i_1 < i_2+1$ or $j_1<j_2+1$ \begin{align} &T(i_1, i_2, j_1, j_2)\\ &= \min\big\{\underbrace{\min_{i_1\leq i<i_2}\left\{T(i_1,i, j_1, j_2) + T(i,i_2, j_1, j_2)\right\}}_{\text{Horizontal splits}}, \underbrace{\min_{j_1\leq j<j_2}\left\{T(i_1,i_2, j_1, j) + T(i_1,i_2, j, j_2)\right\}}_{\text{Vertical splits}}\big\} + 1 \end{align}
Initial conditions (splitting two blocks): \begin{align} T(i, i+2, j, j+1) &= \begin{cases} 0 & \text{if $C(i,j) = C(i+1,j)$}\\1 &\text{otherwise}\end{cases}\\ T(i, i+1, j, j+2) &= \begin{cases} 0 & \text{if $C(i,j) = C(i,j+1)$}\\1 &\text{otherwise}\end{cases} \end{align} All other bases cases are $0$, e.g., $T(i, i+1, j, j+1)$ represents the square between $(i,j)$ and $(i+1,j+1)$ is a unique type of chocolate as it is a single block, so $T(i, i+1, j, j+1)=0$.