摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法: 數學(DP)  //此題解法是上網搜到的

http://nccur.lib.nccu.edu.tw/bitstream/140.119/32573/7/75101807.pdf

這題公式跟(二元樹有N個節點能建多少不同的樹是很像的↑)
只是首項有些許的不同...在此由於也是猜出來的,所以其道理不做說明 =    =+

/**********************************************************/

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
main()
{
  int N;
  while(scanf("%d",&N)==1)
      {
         int a,b,SUM=0;
         long long DP[10001],k;
         DP[1]=1,DP[2]=2;
         for(a=3;a<=N;a++)
            {
            for(b=1,k=0;b<a;b++)
               k=(k+DP[b]*DP[a-b])%1000000000;
              DP[a]=(DP[a-1]+k)%1000000000;
            }
          printf("%I64d\n",DP[N]);
      }
  return 0;
}

精簡修正版↓

/***********************************************************/

#include<stdlib.h>
#include<stdio.h>
main()
{
  int N,a,b;
  while(scanf("%d",&N)==1)
      {
         long long DP[10001],k;
         DP[1]=1,DP[2]=2;
         for(a=3;a<=N;a++)
            {
              int n=a/2-(a%2==0);
              for(b=1,k=0;b<=n;b++)
                  k=(k+DP[b]*DP[a-b])%1000000000;
              k*=2,k%1000000000;
              if(a%2==0) k+=(DP[a/2]*DP[a/2]);
              DP[a]=(DP[a-1]+k)%1000000000;
            }
          printf("%I64d\n",DP[N]);
      }
  return 0;
}