數的劃分-遞推動態規劃

又一經典問題，noip2001。

用到了分類的思想。對于f[i][j]代表i分為j份。我們分為以下兩類：

1. 每份都沒有1：那么我們只需要將每份都減1然后保證有j份。即加上f[i-j][j]。
2. 至少有一份1：那么我們提出1個1,即加上f[i-1][j-1]。

  1: #include <stdio.h>
  2: #define maxn 300
  3: 
  4: int f[maxn][maxn];
  5: int n,m;
  6: 
  7: int main()
  8: {
  9:     scanf("%d%d",&n,&m);
 10:     f[0][0]=1;
 11:     for (int i=1;i<=n;++i)
 12:         for (int j=1;j<=m;++j)
 13:             if (i-j>=0)
 14:                 f[i][j]=f[i-j][j]+f[i-1][j-1];
 15:     printf("%d\n",f[n][m]);
 16:     return 0;
 17: }
 18: 

posted on 2010-08-28 11:04 Sephiroth Lee 閱讀(498) 評論(0)  編輯 收藏 引用 所屬分類: 信息奧賽