模拟赛题, 给出两个长为$n$的数组$a$和$b$, 求出$\displaystyle \sum_{i = 1}^{n} \max(a_{i}, b_{i})$.

正解显然是$O(n)$, 但是考虑DFS.

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)$, 再考虑优化.

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)$, 为什么会出这样的问题?