关于递归的问题，尝试安排最大事件数

Question

我正在研究递归，试图更好地利用它。我当前的活动是尝试编写一种递归方法来生成可以安排的最大数量的事件。到目前为止，这是我的方法：

 public int maxEvents(int n, int[] Start) {
  if(n<=0) return 0;
  if(n==1) return 1;
  else return maxEvents(n-1, Start) + maxEvents(Start[n]-1, Start);
 }

基本上，我的主要方法向 maxEvents 传递一个 int n，这是最后一个事件。假设我有 4 个事件 (1-4)，那么 n 将为 4。下一部分是一个数组，索引处的值是事件开始的时间，索引本身是事件结束的时间。

先决条件是：

n >= 0

天，惯例从 1 到 n

事件 n 于（并包括）第 n 天结束，并于 Start[n] 开始

Begin[0] 未使用

对于所有 i从 1 到 n，Begin[i] <= i （当然，约定我的开始日不能晚于结束日。）

最后我的方法应该返回：

如果您必须仅从会议 1 到 n 中进行选择，则可以主办的会议的最大数量。 （如果 n = 0，则此集合为空）

一些示例输入/输出：

n = 3 Begin[1]=1 Begin[2]=1 Begin[3]=3

maxEvents=2

或者：

n = 5 Begin[1]=1 Begin[2]=1 Begin[3]=2 Begin[4]=3 Begin[5]=4

maxEvents=3

---

我的两次递归调用应该统计最大数量而不邀请n，可以然后从1到n-1中选择。并计算邀请n的最大数量，注意Begin[n]-1是与约定n的开头不冲突的最后一个约定。然后我可以取两者中的最大值，然后返回。

我尝试过使用不同的 if 语句，例如：

if("recursion call 1">"recursion call 2"){ 返回“递归调用1”； 并

使用类似“maxEvents(Start[n]-1, Start)”作为我的递归调用之一（如我上面的代码中使用的），但它没有返回正确的值，就像我上面列出的值一样。总而言之，我在递归的概念上遇到了麻烦，而且我知道我的递归调用出了问题，所以如果有人能指出我正确的方向，那就太好了。谢谢！

Answer 1

这有效吗？

return Math.max(maxEvents(n-1, Start), 1 + maxEvents(Start[n]-1, Start))

这个想法是，您将分成两种互斥的情况：一种是不包含第 n 个事件，另一种是包含第 n 个事件。在两者中，您必须选择更大的。所以将两者相加是不正确的——取最大值才是正确的方法。但您还必须在第二个选项中添加 1 以考虑包括第 n 个事件。