HDU 2067ウサギの碁盤

Description
ウサギのおじさんは外から旅行から帰ってきてプレゼントを持ってきて、ウサギは喜んで自分の部屋に帰って、開けてみると碁盤で、ウサギはがっかりしました.しかし、数日もしないうちに碁盤の面白さを発見しました.起点(0,0)から終点(n,n)までの最短経路数はC(2 n,n)で、今ウサギはまた対角線(ただし対角線上の格子点に触れることができる)を通り抜けなければ、このような経路数はいくらあると思いますか?ウサギは長い間考えていたが、今はウサギにこの問題を解決してもらいたいと思っています.あなたにとって難しくないでしょう.
 
Input
1個の数n(1<=n<=35)を入力する毎に、nが−1に等しいときに入力を終了する.
 
Output
各入力データ出力パス数について、具体的なフォーマットはSampleを参照してください.
 
Sample Input
1 3 12 -1
 
Sample Output
1 1 2 2 3 10 3 12 416024
 
簡単なダイナミックプランニングは、入門に向いていますね.前からダイナミックプランニングをしていましたが、トレーニング試合で出会ったとは思いませんでした.
これは1つの境界でしょう、理论の学习から水题に変わって突然1つのとても面白い比喩を思い付いて、アルゴリズムの难易度は1人の女の人の服で、1人の男の人の考えはすべてこの服の上で、しかし得たいのはこの服ではありません.
アルゴリズムの難易度はある程度私の好きな原因で、ははは、本当に皮肉ですね.

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 long long dp[40][40];
 6 int main()
 7 {
 8     int n;
 9     int t=1;
10     for(int i=1;i<=36;i++)
11         dp[i][0]=1;
12     for(int i=1;i<36;i++)
13     {
14         for(int j=1;j<36;j++)
15         {
16             if(i==j) dp[i][j]=dp[i][j-1];
17             else
18                 dp[i][j]=dp[i-1][j]+dp[i][j-1];
19         }
20     }
21     while(cin>>n&&n!=-1)
22     {
23         cout<<t++<<" "<<n<<" ";
24         cout<<2*dp[n][n]<<endl;
25     }
26 }

この問題を簡単に紹介します.
最短経路が要求されているので、繰り返してはいけないので、端の格子には1つの経路しかありません(起点からどんなに遠くても)、この条件は既知とすることができます.また、対角線の処理、問題では対角線を越えてはいけないことが要求されています.
まず、ある格子を通過したということを考えてみましょう.一つから一つの格子までのすべての経路数を加えて、この格子を通過したとしても、今では対角線を通過しないことをうまく処理することができます.対角線を通過した経路数を加えないだけでいいです.もう一つ言いたいのは、下へ行く過程だからです.上三角形のパス数は下三角形に加算されません.終点が対角線上にあるため、計算中に半分の経路数しか計算されず、なぜ半分なのか、それとも対角線分割が上下の経路数対称なのか.言うべきことはこれだけのようだが,どうせ水の問題だ.