Determine the critical height with O(c) space (22.39 in v1.5.1)

#1

In the book, the solution uses memoization, requiring O(cd) space. When I solved it, I started with a bottom-up tabulation and noticed that only the previous row is necessary for each iteration, leading to O(d) space.

int GetHeight(int cases, int drops) {
  if (cases <= 0 || drops <= 0) return 0;
  if (cases == 1) return drops;
  if (drops == 1) return min(cases, drops);

  vector<int> last_row, cur_row;

  for (int d = 0; d < drops; ++d)
      last_row.push_back(d + 1);

  for (int c = 2; c <= cases; ++c) {
      cur_row = { 1 };

      for (int d = 1; d < drops; ++d)
          cur_row.push_back(last_row[d - 1] + cur_row.back() + 1);

      last_row = move(cur_row);
  }

  return last_row.back();
}

Though, it seems that in most nontrivial cases d >> c, so O© space would probably be better.

int GetHeight(int cases, int drops) {
  if (cases <= 0 || drops <= 0) return 0;

  vector<int> row(cases, 0);

  for (int d = 0; d < drops; ++d) {
    for (int c = cases - 1; c >= 0; --c)
      row[c] += (c == 0 ? 0 : row[c - 1]) + 1;
  }

  return row.back();
}

The code is also cleaner above because I was able to avoid the two row approach by working backwards.

1 Like
#2

Hey Corwin,

Great, and this is actually very nice code that matches many other implementations in DP chapter that optimize space complexity without losing the time complexity.

0 Likes