【noi 2.7_7215】简单的整数划分问题（算法效率）

题意：问正整数n的所有划分个数。

解法：f[i][j]表示划分 i 后的每个数不大于 j 的划分数。分情况讨论：划分中每个数都小于 j，相当于每个数不大于 j- 1, 故划分数为 f[i][j-1] 或划分中至少有一个数为 j. 相当于把剩下的 i-j 进行划分，每个数不大于j，划分数为 f[i-j][j]。

注意——“若干”组测试数据；这题方程列出来之后调对也不容易，i<j时也有值，f[i-j][j]只要 i>=j 就可以调用了。于是我有2种打法。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 int f[55][55];
 8 
 9 int main()
10 {
11     int n;
12     while(~scanf("%d",&n))
13         {
14      for (int j=0;j<=n;j++) f[0][j]=1;
15      for (int i=1;i<=n;i++)
16      {
17        f[i][1]=1;
18        for (int j=2;j<=n;j++)//
19        {
20         f[i][j]=f[i][j-1];
21         if (i>=j) f[i][j]+=f[i-j][j];
22        }
23      }
24      printf("%d
",f[n][n]);
25         }
26     return 0;
27 }

View Code 1

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 int f[55][55];
 8 
 9 int main()
10 {
11     int n;
12     while (~scanf("%d",&n))
13     {
14      for (int i=1;i<=n;i++)
15      {
16       f[i][1]=1;
17       for (int j=2;j<=n;j++)//
18       {
19         if (i<j) f[i][j]=f[i][i];
20         if (i==j) f[i][j]=f[i][j-1]+1;
21         if (i>j) f[i][j]=f[i][j-1]+f[i-j][j];
22       }
23      }
24      printf("%d
",f[n][n]);
25     }
26     return 0;
27 }

View Code 2

附上更多的学习，见【noi 2.6_8787】数的划分（DP）｛附【转】整数划分的解题方法｝ http://www.cnblogs.com/konjak/p/5950919.html 。