Compute how to subdivide an n m marble slab to maximize your proﬁt You have mined a large slab of marble from your quarry. For simplicity,
suppose the marble slab is a rectangle measuring n inches in height and m inches in width. You
want to cut the slab into smaller rectangles of various sizes – some for kitchen countertops, some
for large sculpture projects, others for memorial headstones. You have a marble saw that can make
either horizontal or vertical cuts across any rectangular slab. At any given time, you can query the
spot price px,y of an x  y marble rectangle, for any positive integers x and y. These prices will
vary with demand, so do not make any assumptions about them. Given the spot prices, describe
an algorithm to compute how to subdivide an n  m marble slab to maximize your proﬁt.
 A: Let $M[n,m]$ represent the maximum profit that can be obtained by subdividing an $n \times m$ marble slab. Then using the provided spot price function $p(x,y)$, we observe that if $n=0$ or $m=0$, then $M[n,m] = 0$; otherwise, we have that $M[n,m]$ is:
$$
\max\left\{p(n,m),~~\max\limits_{1\leq i\leq \left\lfloor\frac{n}{2}\right\rfloor}\{M[i,m] + M[n-i,m]\},~~\max\limits_{1\leq j\leq \left\lfloor\frac{m}{2}\right\rfloor}\{M[n,j] + M[n,m-j]\}\right\}
$$
Intuitively, this is saying that we can either sell the entire slab, make some horizontal cut, or make some vertical cut. We describe this recursion by using the following dynamic programming algorithm:
COMPUTE-M(n,m,p,M)
    if (M[n][m] != NIL) then:
        return // Don't redo work.
    else if (n == 0  or  m == 0) then:
        M[i][j] <- 0 // Base Case.
    else:
        max <- 0
        for i <- 1 to floor(n/2) do: // Check all horizontal cuts.
            COMPUTE-M(i,m,p,M)
            COMPUTE-M(n-i,m,p,M)
            if (M[i][m] + M[n-i][m] > max) then:
                max <- M[i][m] + M[n-i][m]
        for j <- 1 to floor(m/2) do: // Check all vertical cuts.
            COMPUTE-M(n,j,p,M)
            COMPUTE-M(n,m-j,p,M)
            if (M[n][j] + M[n][m-j] > max) then:
                max <- M[n][j] + M[n][m-j]
        if (p(n,m) > max) then: // Should we just sell the entire slab?
            max <- P(n,m)
        M[n][m] <- max

Finally, we initiate everything using the following:
SUBDIVIDE(n,m,p)
    // Initialize M to be completely NIL.
    for i <- 0 to n do:
        for j <- 0 to m do:
            M[i][j] <- NIL
    COMPUTE-M(n,m,p,M)
    // Return the maximum profit and the list of slabs.
    return M[n][m]

