Dynamic programming: Do I have overlapping sub-problems?

Question

My algorithm

Let us assume I have an 2D array of real numbers. I start at a specific cell in this array with a particularly large number in it. I want to mark which of the other cells should belong to the mentioned start cell. The rule is this: The other cell belongs to the start cell if I find a way to walk from the start cell to the other cell. I am only allowed to walk a cell up or down. I am only allowed to walk from a cell with a higher number to a cell with a lower number. Here is an example when I start at the center 9

My pseudo-algorithm is

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

Now comes a second aspect, that I do not only do this for one start cell, but for multiple start cells, for example

Dynamic Programming

I researched dynamic programming and found that two conditions need to be meet in order to be able to apply dynamic programming:

subproblems need to be overlapping
subproblems need to have optimal substructure

"[dynamic programming] refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner [...] If a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure. [...] There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead. This is why merge sort and quick sort are not classified as dynamic programming problems. Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. Such optimal substructures are usually described by means of recursion. [...] Overlapping sub-problems means that the space of sub-problems must be small, that is, any recursive algorithm solving the problem should solve the same sub-problems over and over, rather than generating new sub-problems."Wikipedia

I was wondering whether my algorithm is dynamic programming. It is definitely recursive and it seems to be optimal in substructure. I am starting to wonder about the overlapping substructure though. There is an example with Fibonacci numbers, but it seems to me that the key aspect is that intermediate results of the recursive algorithm can be stored. For my algorithm intermediate results cannot be stored - at least not for one run of a single start cell. However, when I consider the entire problem, with many start cell, we see that some of the area is connected:

Lets say we start with the orange 9 in the left image and go down the green path until we reach in blue 5. From there we can also get to the blue 3 and the blue 2. We finish our algorithm for the left orange 9.

Now we turn to the lower orange 8 in the right image. We start from this 8 and go up the green path to the green 6. From there we get to the blue 5. We already know from the previous computations (from the orange 9 in the left image) that the blue 3 and the blue 2 are reachable from the blue 5, so we can just mark them in one swoop, without recalculating the path.

That is why I think that my overall problem is solvable with dynamic programming.

Questions

Is my algorithm / problem dynamic programming? Why, why not?
If not, can I make it to be dynamic programming and if so how?

Matt Timmermans Matt Timmermans · Accepted Answer · 2018-10-11T13:02:48

Yes, this is certainly a dynamic programming problem. It's actually the simplest/most fundamental dynamic programming problem -- find all the nodes reachable from a start node in a directed acyclic graph (multiple start nodes in your case). You solve it with depth-first search or breadth-first search.

It fits the definition like this:

Optimal structure? Yes, the cells I can reach from a cell x is x plus the union of the cells I can reach from x's smaller neighbors.

Overlapping subproblems? Yes, two of x's neighbors can both share the same smaller neighbor.

In order to make your posted algorithm into a dynamic programming algorithm you just need to memoize the subproblems like this:

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr) AND cell_is_not_marked(neighborNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

Note that this also changes your algorithm from exponential time to linear time, and that it is a depth-first-search

Dynamic programming: Do I have overlapping sub-problems?

My algorithm

Dynamic Programming

Questions

1 Answers