PKU 1243 One Person

http://poj.org/problem?id=1243
以下のようなルールで数字あてゲームをする。
最初参加者はguessポイントとlifeポイントを持っている。
そして、guessポイントをひとつ消費してある数字が、答えの数字と同じか、それより小さいか、それより大きいかを聞くことができる。
答えと同じであれば参加者が勝利する。
また、答えの数字より大きかった場合lifeポイントをひとつ失う。

ここで、guessポイントを使いきっても正解できなかったり、lifeポイント0の状態で答えの数字より大きい数字を尋ねてしまうと負けになる。

このとき、あるguessポイントGとlifeポイントLで確実に正解できるのは数字の上限が1からいくつまでの時かを答えろというような問題。

あるguessポイントGとlifeポイントLで答えられる数字の個数は
1+(G-1のguessポイントとL-1のlifeポイントで答えられる数字の個数)+(G-1のguessポイントとLのlifeポイントで答えられる数字の個数)で表すことができるということに気づけたので解けました。

ll memo[40][40];
bool vis[40][40];

ll rec(int L,int G){
  if(!L)return G;
  if(G==1)return 1;
  if(vis[L][G])return memo[L][G];
  vis[L][G]=true;
  return memo[L][G]=1+rec(L,G-1)+rec(L-1,G-1);
}

main(){
  int l,g;
  int ca=0;
  while(cin>>g>>l,l|g)printf("Case %d: %lld\n",++ca,rec(l,g));
}