Recently I'm learning a new strategy known as dynamic programming (DP) and greedy algorithm in algorithm course. However I'm having some trouble. Here is a coding assignment and for which I have no idea whether DP is the correct strategy, here is the problem:

There are N villages lined up in a row. In these villages, some of them need to be selected to build base stations, where the coverage radius of each base station is R. Suppose a base station is placed at village i, and the coordinate of village i is X_i ​ , then in [X_i - R, X_i R], villages can be covered by this base station. Given the coordinates of all villages, find the minimum number of base stations required for all villages to be covered by base stations.

Suppose the input N_i's are monotonically increasing. I'm trying to solve this problem by DP strategy, by constructing a 2d array dp[i][j], where i = 1, 2, ..., N and j = 1, 2, ..., R, in order to record the minimum number of base stations required when there are i villages and the covering radius is j. But I'm not sure how to find the recursive formula this way.

Is there something wrong with my array construction? Or DP is not the best choise there? Any help is appreciated!!

CodePudding user response：

Let's analyse your DP approach first:

1. Why do you need a second parameter j for covering radius, since that is a fixed value R for all stations?
2. Let's say dp[i 1] = count of stations to cover villages (i 1)..n. While calculating dp[i], you'll need to keep a track of the outermost range till now (that is, for any existing station in i 1...n, will i be covered in it's range or not)

To remove these unncessary complications, we can actually remove the dynamic programming approach by looking at a greedy property. The range of each station is 2*R (R in each direction). So, starting with the first village, see how many villages get covered in the 2*R range. For the first house outside this range, increment the station count, and repeat the approach.

In my opinion, DP seems like a convoluted approach to solve a simple problem which can be done in O(n) time and constant space for a sorted input.

Edit:
To clear the confusion: if there are overlapping sub-problems in the greedy solution, then it makes sense to use DP. There is no point in storing results of sub-problems if they never overlap, since that means they'll only be computed once.
Greedy and DP don't conflict/contradict, they can be used simultaneously.