メモ化再帰のキャッシュは処理の最初でやる

　メモ化再帰で答えをキャッシュする場合、

1. 処理の最後にキャッシュする
2. 処理の最初にキャッシュする

という２つの書き方がある。自分はだいたい前者の書き方で書いていた。

このような感じ。

int dp[100][100];

int rec(int x, int y) {
  if (dp[x][y] != -1)
    return dp[x][y];

  int ret = 0;
  // do some calculation                                                                                                       

  return dp[x][y] = ret;
}

しかし上のような書き方だと、// do some calculationの中でx, yの値を書き換えてしまうとバグってしまう。

まあ落ち着いていればそのようなミスはないかもしれないが、コンテスト本番で慌てているとそのようなミスが発生するかもしれない。// do some calculationの処理が長くて複雑な場合はすぐにバグの原因を発見できないかもしれない。

このようなバグを予防するには、以下のような後者の書き方の方が良さそうだ。

int dp[100][100];

int rec(int x, int y) {
  int &ret = dp[x][y];
  if (ret != -1)
    return ret;

  ret = 0;
  // do some calculation                                                                                                       

  return ret;
}

というちょいTIPSな話でした。