At least how many lines are needed to reduce the number in the grid to zero

user_16656750 0
Viewed 53

This is a programming problem.

Suppose we have an n x m array, and each grid contains an integer greater than or equal to 0.

enter image description here

We can choose to draw a vertical line or a horizontal line. In the grid where this line passes, the number in it will be reduced by one (not less than 0).

Example: If we draw a horizontal line.

enter image description here

So how many lines do we need at least to reduce the numbers in the grid to zero?

I have thought about using brute force search method and dynamic programming method But there is no clear proof to prove that my idea is right.

Can someone help me solve this problem? thanks.

algorithm
1 Answers

I think that the dynamic programming approach is rather clear and provable.

You start with a singleton list of your start grid.

At each stage, you take each grid in the current list and for each row and column in that grid that isn't already completely zero produce a new grid that has all cells in this row or column reduced by one. Then remove duplicates. Count the stages until you have the all-zero grid.

This can be optimized by only producing two new grids for each grid, choosing either a row or column for the highest remaining cell.

Harleqin_316150
Related