# Dynamic Programming to Maximize Profit

I have this problem to resolve in dynamic programming:

An ice cream shop owner has 4 stores. To meet the demand in the summer he purchased 7 refrigerators for the ice cream. Because the stores are in different places, there are different points for selling the ice cream. It was estimated the profit (in monetary unit) that could be obtained in each store:

$$\begin{array}{c|lcr} N refrigerators & \text{store1} & \text{store2} & \text{store3} & \text{store4} \\ \hline 1 & 4 & 2 & 6 & 1 \\ 2 & 6 & 6 & 12 & 4 \\ 3 & 10 & 8 & 14 & 8 \\ 4 & 12 & 10 & 18 & 16 \\ 5 & 14 & 12 & 20 & 20 \\ 6 & 16 & 16 & 22 & 21 \\ 7 & 18 & 20 & 22 & 24 \end{array}$$

The problem asks to find the working scheme that maximizes the financial return.

As dynamic programming aims to reuse the code I know that it is necessary to use a recursive function, but when analyzing the problem I assumed that my answer field is in a matrix where the lines are referring to the number of refrigerators and the columns the stores.

Then I assumed that $M(i, j)$ is my function that returns a monetary value, assuming that $i$ is the number of refrigerators, ranging from $1 \le i \le 7$, and $j$ is a particular store, ranging from $1 \le j \le 4$.

I also assumed that my function would have 4 calls of this same function $M(i, j)$, because there are 4 stores to divide 7 refrigerators:

The equation would be:

$$MAX \{ M(i, 1) + M (i, 2) + M (i, 3) + M (i, 4)\}$$

Where $\sum_{i=1}^4 i \le 7$

As a base case of recursion I put this:

$$M(0, 1) + M (0, 2) + M (0, 3) + M (0, 4) = 0$$

But my problem is not knowing how to treat this problem recursively. Maybe I'm doing the wrong analysis, too. Every help is welcome.

The dynamic programming approach is to compute recursively the maximal profit that can be obtained from using $x$ refrigerators in the first $y$ stores (and not using any in the other stores). I'll let you fill in the missing details.