基站动态规划问题构建
Dynamic programming problem constructing of base station
最近我在算法课程中学习了一种新的策略，称为动态规划（DP）和贪心算法。但是我遇到了一些麻烦。这是一个编码作业，我不知道 DP 是否是正确的策略，这是问题所在：
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.
假设输入 N_i 是单调递增的。我试图通过 DP 策略解决这个问题，通过构造一个二维数组 dp[i][j]，其中 i = 1, 2, ..., N 和 j = 1, 2, ..., R，依次记录有i个村庄，覆盖半径为j时，最少需要的基站数。但是我不确定如何通过这种方式找到递归公式。
我的数组构造有问题吗？还是 DP 不是最好的选择？感谢您的帮助！！
先分析一下你的DP方法：
- 为什么你需要第二个参数
j 作为覆盖半径，因为它是所有站点的固定值 R？
- 假设
dp[i+1] = count of stations to cover villages (i+1)..n。在计算 dp[i] 时，您需要跟踪最外面的范围直到现在（即，对于 i+1...n 中的任何现有站点，i 是否会被覆盖在其范围内或不)
为了消除这些不必要的复杂性，我们实际上可以通过查看贪心 属性 来消除动态规划方法。每个站的范围是2*R (R in each direction)。因此，从第一个村庄开始，找到距离最远 R 最右边的村庄，并在那里添加一个站点。看看现在有多少个村庄被覆盖在这个站右边的 R 范围内。对于此范围外的第一个房子，增加站数，然后重复该方法。
在我看来，DP 似乎是一种解决简单问题的复杂方法，可以在 O(n) 时间和常量 space 中完成排序输入。
编辑：
澄清一下：如果贪心解中有重叠 sub-problems，那么使用 DP 是有意义的。如果 sub-problems 的结果从不重叠，那么存储它们就没有意义，因为这意味着它们只会被计算一次。
Greedy和DP不用conflict/contradict，可以同时使用
最近我在算法课程中学习了一种新的策略，称为动态规划（DP）和贪心算法。但是我遇到了一些麻烦。这是一个编码作业，我不知道 DP 是否是正确的策略，这是问题所在：
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.
假设输入 N_i 是单调递增的。我试图通过 DP 策略解决这个问题，通过构造一个二维数组 dp[i][j]，其中 i = 1, 2, ..., N 和 j = 1, 2, ..., R，依次记录有i个村庄，覆盖半径为j时，最少需要的基站数。但是我不确定如何通过这种方式找到递归公式。
我的数组构造有问题吗？还是 DP 不是最好的选择？感谢您的帮助！！
先分析一下你的DP方法：
- 为什么你需要第二个参数
j作为覆盖半径，因为它是所有站点的固定值R？ - 假设
dp[i+1] = count of stations to cover villages (i+1)..n。在计算dp[i]时，您需要跟踪最外面的范围直到现在（即，对于 i+1...n 中的任何现有站点，i是否会被覆盖在其范围内或不)
为了消除这些不必要的复杂性，我们实际上可以通过查看贪心 属性 来消除动态规划方法。每个站的范围是2*R (R in each direction)。因此，从第一个村庄开始，找到距离最远 R 最右边的村庄，并在那里添加一个站点。看看现在有多少个村庄被覆盖在这个站右边的 R 范围内。对于此范围外的第一个房子，增加站数，然后重复该方法。
在我看来，DP 似乎是一种解决简单问题的复杂方法，可以在 O(n) 时间和常量 space 中完成排序输入。
编辑：
澄清一下：如果贪心解中有重叠 sub-problems，那么使用 DP 是有意义的。如果 sub-problems 的结果从不重叠，那么存储它们就没有意义，因为这意味着它们只会被计算一次。
Greedy和DP不用conflict/contradict，可以同时使用