There is a m*n matrix, wich include the many buildings. We have two different kind of bomb : bomb1 can only destroy 1 building, bomb2 can destroy buildings within a radius of k. The cost of the two different bombs are 1 and 2.

Find the min cost to destroy all of the building.

For example , the buildings(A,B,C) and k=2, layout: just like below,
If we put Bomb1 at A,B,C then the cost is 1+1+1=3
If we put Bomb2 at A, then A, B are destroyed , then put Bomb1 at C, the cost is 2+1=3
If we put Bomb2 at B, then A,BC are destroyed, the cost is 2.

So the min cost is 2.
[* * A * B * C*]

1 How can we solve this problem ?
2 Can we solve this one use DP?