CODEWITHSUNDEEP
pythonalgorithmdynamic-programming
Jir
Jir

Reputation: 3125

How to find the minimum number of tiles needed to cover holes in a roof

I'm just learning about dynamic programming, and I've stumbled upon a problem which I am not sure how to formulate in Python:

Given a binary array H of length 55, a 1 indicates a hole in the roof, 0 indicates no hole. The tails you can use have length 1, 13 or 55, and the cost to deploy each is 3, 13 and 50, respectively. For a given array of holes H return the minimum cost such that all the holes are covered.

From what I learned, the first step is to find the base cases, and to reason by induction. So, here are some base cases I could easily find:

Initially I thought the first point means that if there are 5 or more holes in 13 contiguous spaces I should always choose the 13 tile. However I think it depends on following holes.

The second point is even more problematic if you throw in 1-tiles in the problem. Consider, e.g., 4 single holes at locations [0, 15, 29, 44] you're better off with 4 1-tiles (1 x 55-tile costs 50, 4 x 13-tiles = 52).

So it looks I have to evaluate "how spaced" are the holes for all the possible combination of slices in the array are.

How can I formulate the above into (even pseudo-) code?

Upvotes: 1

Views: 1359

Answers (1)

serhiyb
serhiyb

Reputation: 4833

Lets say cost[i] - best cost to cover first i elements of the roof. Obviously cost[0] = 0 (we don't need any money to cover 0 tiles).

Lets describe our state as (position, cost).

From state (i,cost[i]) we can get to 4 different potential states:

  • (i + 1, cost[i] + 3) (when we use tile of length 1 and cost is 3)
  • (i + 13, cost[i] + 13) (tile length = 13, cost is also 13)
  • (i + 55, cost[i] + 50) (tile length = 55, cost is 50)
  • (i + 1, cost[i]) (we ignore current position and don't use any tile here)

Once we change state using one of the above rules we should consider:

  • position should be <= total Length (55)
  • if we get to position i with same or bigger cost we don't want to proceed (basically dynamic programming plays role here, if we get to the sub-problem with same or worse result we don't want to proceed).
  • we can't skip tile (our 4th state transformation) if this tile has hole.

Once we run all this state transformations answer will be at cost[total length (55)]

Upvotes: 3

Related Questions