Is this problem a variation of another problem?

Dynamic programming requires an optimal substructure. I have not been able to think of one.

My first though was to try to find a solution to an (n-1)x(n-1), and then expand that solution to a n x n. But here is an example of that failing.

2x2, assume c = 3:

1 1
1 0

The optimal solution here is to build walls around the healthy square, at a cost of 2.

But now we expand to a 3x3:

1 1 1
1 0 1
1 1 1

Now the optimal solution is to build nothing, at a cost of c = 3. So our substructure was not optimal.

The approach of expanding an (n-1)x(n-1) into an n x n may still be a good one though. I haven't yet been able to come up with an example where anything in the subproblem needs to change that isn't on the right or bottom edge.

/r/learnprogramming Thread