We have a stack of $n \times n \times n$ cubes, each with a possibly negative cost. You are allowed to remove cubes from the stack, but each remaining cube must have
- a cube immediately below it,
- a cube immediately to the left of it, and
- a cube immediately "inside" of it (or whatever you call the third dimension).
Of course, Condition 1 does not apply to the bottom layer etc. Below is an example that we can think of as a sub-stack of an original stack of $6 \times 6 \times 6$ cubes.
Which cubes should be removed from the stack to find a minimum-cost sub-stack? The two-dimensional case can be solved as a simple shortest path in a graph, but I cannot see how to solve this three-dimensional problem in an efficient way.
