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

Question

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

 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);
 }

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

前提条件是:

n >= 0

日期和惯例从 1 到 n

事件 n 在第 n 天结束(并包括)并在 Start[n] 开始

Begin[0] 未使用

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

最后我的方法应该返回:

如果您必须仅从 session 1 到 n 中进行选择，则可以主办的 session 的最大数量。 (如果 n = 0，则该集合为空)

一些输入/输出示例:

n = 3 开始[1]=1 开始[2]=1 开始[3]=3

最大事件数=2

或者:

n = 5 开始[1]=1 开始[2]=1 开始[3]=2 开始[4]=3 开始[5]=4

最大事件数=3

<小时/>

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

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

if("递归调用1">"递归调用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 个事件。