关于dfs

模拟赛题, 给出两个长为

n

的数组

a

和

b

, 求出

\displaystyle \sum_{i = 1}^{n} \max(a_{i}, b_{i})

正解显然是

O(n)

, 但是考虑DFS.

CPP

int dfs(int i, int s) {
  if (i == n + 1) {
    return s;
  }
  return max(dfs(i + 1, s + a[i]), dfs(i + 1, s + b[i]));
}

很明显是

O(2^n)

, 再考虑优化.

CPP

int dfs(int i, int s) {
  if (i == n + 1) {
    return s;
  }
  return dfs(i + 1, s + max(a[i], b[i]));
}

根据DFS时间复杂度

= O(k ^ n)

其中

k

是状态数, 很明显是

O(1^n) = O(1)

, 然而稍微一分析就想到是

O(n)

, 为什么会出这样的问题?

讨论操作