Problem E

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
Aunt Lizzie takes half a pill of a certain medicine every day. She starts with a bottle that contains N pills.

On the first day, she removes a random pill, breaks it in two halves, takes one half and puts the other half back into the bottle.

On subsequent days, she removes a random piece (which can be either a whole pill or half a pill) from the bottle. If it is half a pill, she takes it. If it is a whole pill, she takes one half and puts the other half back into the bottle.

In how many ways can she empty the bottle? We represent the sequence of pills removed from the bottle in the course of 2N days as a string, where the i-th character is W if a whole pill was chosen on the i-th day, and H if a half pill was chosen (0 <= i < 2N). How many different valid strings are there that empty the bottle?
 

 

Input
The input will contain data for at most 1000 problem instances. For each problem instance there will be one line of input: a positive integer N <= 30, the number of pills initially in the bottle. End of input will be indicated by 0.
 

 

Output
For each problem instance, the output will be a single number, displayed at the beginning of a new line. It will be the number of different ways the bottle can be emptied.
 

 

Sample Input
6 1 4 2 3 30 0
 

 

Sample Output
132 1 14 2 5 3814986502092304
 
 
相當于求N個W，和N個H的排列數，而且要求前面任意個中必需H的個數不大于W的個數~~~~
不知道哪些大神是怎么樣做出來的，好快的速度就做出來了~~~~
 
我想了好久都沒有想到DP的方法，
最后想出來了，感覺方法比較笨~~~~
 
轉化成了圖，W表示往下走，H表是往右走，
則必須在左下角中。
N個W和H的時候就是到N-1行的路徑數
如N=1時，為dp[0,0]
N=2時為dp[1,0]+dp[1,1]
N=3時為dp[2,0]+dp[2,1]+dp[2,2]
 
 
應該會有更好的方法的~~~~~
我的思路有點蹉了~~~~但幸好做出來了！
 
代碼如下：
#include<stdio.h>
long long dp[31][31];
void init()
{
    dp[0][0]=1;
    for(int i=1;i<31;i++)
    {
        dp[i][0]=1;
        for(int j=1;j<i;j++)
          dp[i][j]=dp[i-1][j]+dp[i][j-1];
        dp[i][i]=dp[i][i-1];
    }   
} 
int main()
{
    int N;
    init();
    while(scanf("%d",&N),N)
    {
        printf("%I64d\n",dp[N][N]);
    }    
    return 0;
}
要求的其實就是從（0，0）到(N,N)的路徑數，只能往下或者往右走，而且不能走到右上部分去。

文章來源:http://www.cnblogs.com/kuangbin/archive/2012/03/03/2378248.html