HDU 2067ウサギの碁盤

http://acm.hdu.edu.cn/showproblem.php?pid=2067
この問題の状態は私はずっと前から分析して、1本のプッシュ問題で、当初は思考が乱れて書いていないと感じました.今日はダイナミックプランニングをよく検討したところ,ダイナミックプランニングで検索を記憶化する考え方でこの問題を解決できることが分かった.


View Code

#include <stdio.h>
#include <string.h>
int n,flag=1; 
__int64 d[100][100]; 
__int64 f(int i,int j) 
{ 
    if(d[i][j]>=1)return d[i][j]; 
    if(j==1)return d[i][j]=i;
    if(i==j)return d[i][j]=f(i,j-1); 
    return d[i][j]=f(i-1,j)+f(i,j-1);
} 
int main() 
{ 
    while(scanf("%d",&n)) 
    { 
        if(n==-1)break; 
        memset(d,0,sizeof(d)); 
        printf("%d %d %I64d
",flag,n,2*f(n,n));
        flag++; 
    } 
    return 0; 
}