Introduction: total time limit: 100ms memory limit: 65536kB Description: the positive integer n is expressed as the sum of a series of positive integers, n=n1+n2 +... + nk, where N1 > = N2 > =... > = nk > = 1, k > = 1. This representation of positive integer n is called the partition of positive integer n.
Total time limit: 100ms memory limit: 65536kB
describe
The positive integer n is expressed as the sum of a series of positive integers, n=n1+n2 +... + nk, where N1 > = N2 > =... > = nk > = 1, k > = 1.
This representation of positive integer n is called the partition of positive integer n. The number of different partitions of positive integer n is called the partition of positive integer n.
input
The standard input contains several sets of test data. Each set of test data is an integer n (0 < n < = 50).
output
For each group of test data, the score of N is output.
sample input
5
sample output
7
Tips
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
Pay attention to the comparison topic:
(1)Division of numbers (dividing n into k parts is a bit similar to Put apples , but for the problem of putting apples, the plate can be empty, it is not allowed to be empty.)
Algorithm (I) recursive method
Write a positive integer n as follows: n = M1 + M2 ++ mi; (where MI is a positive integer and 1 < = Mi < = n), then {m1,m2,...,mi} is a partition of n. If the maximum value in {m1,m2,...,mi} does not exceed m, that is, max (m1,m2,...,mi) < = m, it is said to belong to an M division of n. Here we note that the number of M partitions of n is f(n,m);
For example, when n=4, it has five divisions, {4}, {3,1}, {2,2}, {2,1,1}, {1,1,1}; Note that 4 = 1 + 3 and 4 = 3 + 1 are considered the same partition.
According to the relationship between n and m, consider the following situations:
(1) When n=1, there is only one division, namely {1}, regardless of the value of m (m > 0);
(2) When m=1, no matter what the value of n is, there is only one division, that is, n 1, {1,1,1,..., 1};
(3) When n=m, it can be divided into two cases according to whether n is included in the division:
(a). There is only one case where n is included in the partition, that is {n};
(b). When n is not included in the partition, the largest number in the partition must be smaller than N, that is, all (n-1) partitions of n. Therefore, f(n,n) =1 + f(n,n-1);
(4) When n < m, it is equivalent to f(n,n) because negative numbers cannot appear in the division;
(5) However, when n > m, it can be divided into two cases according to whether the maximum value m is included in the division:
(a). If M is included in the partition, that is, {m, {x1,x2,...xi}, where the sum of {x1,x2,... xi} is N-M, M may appear again, so it is an M partition of (n-m), so the number of such partitions is f(n-m, m);
(b). If M is not included in the partition, all values in the partition are smaller than m, that is, the number of (m-1) partitions of n is f(n,m-1); Therefore, f(n, m) = f(n-m, m)+f(n,m-1);
Based on the above situation, we can see that the above conclusion has the characteristics of recursive definition, in which (1) and (2) belong to regression conditions, and (3) and (4) belong to special cases, which will be converted to case (5). Case (5) is a general case and belongs to a recursive method. Its essence is to solve the problem by reducing m to achieve the regression condition. The recursive expression is as follows:
f(n, m) =1; (n=1 or m=1)
=f(n, n); (n<m)
=1+ f(n, m-1); (n=m)
=f(n-m,m)+f(n,m-1); (n>m)
1 #include <stdio.h>
2 long long GetPartitionCount(int n,int max)
3 {
4 if(n==1||max==1) return 1;
5 else if(n<max) return GetPartitionCount(n,n);
6 else if(n==max) return 1+GetPartitionCount(n,max-1);
7 else return GetPartitionCount(n,max-1)+GetPartitionCount(n-max,max);
8 }
9 int main(int argc, char *argv[])
10 {
11 int n;
12 while(scanf("%d",&n)!=EOF)
13 {
14 printf("%lld\n",GetPartitionCount(n,n));
15 }
16 return 0;
17 }
Algorithm (II) dynamic programming
This problem is the division of integers. In fact, the defined state is the recurrence of simple dynamic programming.
We define dp[n][k] to represent the number of schemes that divide N and the maximum number does not exceed K. then we can get the following recursive schemes:
dp[n][k] = dp[n][k-1] + dp[n-k][k];
dp[n][k-1] is the integer division of N, and the maximum number does not exceed the number of schemes of k-1; dp[n-k][k] represents the number of schemes represented by a number not exceeding k after taking out a K.
When k > N, it is the same as the value of dp[n][n]. Next, all solutions are obtained by recursive method, and then the corresponding input n and output dp[n][n].
1 #include<iostream>
2 #include<cstring>
3 #include<cstdlib>
4 #include<cstdio>
5 using namespace std;
6
7 const int MAX = 122;
8 int dp[MAX][MAX];
9
10 void Dynamic()
11 {
12 for(int i=1; i<MAX; i++)
13 {
14 dp[i][1] = dp[1][i] = dp[0][i] = 1;
15 }
16 for(int i=2; i<MAX; i++)
17 {
18 for(int j=2; j<MAX; j++)
19 {
20 if(j<=i) dp[i][j] = dp[i][j-1] + dp[i-j][j];
21 else dp[i][j] = dp[i][i];
22 }
23 }
24 }
25 int main()
26 {
27 int n;
28 Dynamic();
29 while(scanf("%d",&n)!=EOF)
30 {
31 printf("%d\n",dp[n][n]);
32 }
33 return 0;
34 }
The following discussion is more clear about the dynamic planning idea of this problem:
Integer partition problem
The division of number n is to express n as the sum of multiple positive integers. The division can be divided into two cases:
The first case: among the divided multiple positive integers, the number of positive integers is arbitrary.
This can be divided into two categories: positive integers can be the same and different
1. Multiple positive integers divided can be the same, and the recursive equation can be expressed as:
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m]
The analysis dp[n][m] represents the partition of integer n, and each number is not greater than m. Score can be divided into the following two cases:
a. each number in the division is less than m, which means that each number is not greater than m- 1, so the division score is dp[n][m-1]
b. if at least one number in the division is m, subtract m from n, and the rest is equivalent to dividing n-m, so the division score is dp[n-m][m];
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
Where dp[n][m] represents the partition number of integer n, and each number is not less than m. Similarly, the formula can be proved.
2. The divided multiple positive integers are different from each other, and the recursive equation can be expressed as:
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]
Analysis: dp[n][m] represents the partition number of integer n, and each number is not greater than m. Similarly, the division is divided into the following two cases:
a. each number in the division is less than m, which means that each number is not greater than m- 1, and the division number is dp[n][m-1]
b. one number in the division is m. subtract m from n, and the rest is equivalent to dividing N-M, and each number is not greater than M-1, so the division score is dp[n-m][m-1]
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
Where dp[n][m] represents the partition number of integer n, and each number is not less than m.
The second case: among the divided multiple positive integers, the number of positive integers is fixed
The total number of methods for unordered division of an integer n into the sum of K positive integers different from each other. The equation is: dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
Reference to certification method: http://www.mydrs.org/program/html/0369.htm
In another understanding, the general methods can be divided into two categories:
Class I: n copies do not contain 1 points. In order to ensure that each copy is > = 2, k 1 points can be taken out first
To each portion, and then divide the remaining n-k into k portions. The division methods are: dp[n-k][k]
The second category: if at least one of the n copies is 1, you can choose one 1 first as a separate one, and the rest
The N-1 under the table can be divided into k-1 parts. The division methods are: dp[n-1][k-1]
Similar questions:
M balls in N boxes, or apple on a plate. For example: put M balls into N boxes, and allow empty boxes (no balls). How many ways are there? These are typical DP problems.
Use F(m,n) to indicate how many kinds of playback methods there are:
If m=0 or M = 1, f = 1
If n=0 or n=1, F =1
F(0,0) = F(0,1) = F(1,0) = F(1,1) = 1
Otherwise, F = F(m-n,n) + F(m,n-1), which is the recursive solution of DP's solution space
On prime factor and decomposition of integers
[problem description]
Goldbach conjectures that any even number not less than 6 can be decomposed into the sum of two odd primes. If an integer can be expressed as the sum of two or more primes, a prime sum decomposition is obtained. For a given integer, all such prime numbers and factorizations are output. Note that the decomposition of isomorphism is output only once (for example, 5 has only one decomposition 2 + 3, and 3 + 2 is the isomorphic decomposition of 2 + 3).
For example, the integer 8 can be decomposed into the following three types:
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5
[algorithm analysis]
To decompose the specified integer N into the sum of prime numbers, first calculate all prime numbers in the integer N, and then recursively solve all prime numbers and decomposition.
The original author's C + + Code: (I feel that it is actually the idea of backtracking)
1 #include <iostream>
2 #include <vector>
3 #include <iterator>
4 #include <cmath>
5 using namespace std;
6
7 // Calculate all primes in num (excluding Num)
8 void CalcPrimes(int num, vector<int> &primes)
9 {
10 primes.clear();
11 if (num <= 2)
12 return;
13
14 primes.push_back(2);
15 for (int i = 3; i < num; i += 2)
16 {
17 int root = int(sqrt(i));
18 int j = 2;
19 for (j = 2; j <= root; ++j)
20 {
21 if (i % j == 0)
22 break;
23 }
24 if (j > root)
25 primes.push_back(i);
26 }
27 }
28
29 // Output all prime combinations (recursive implementation)
30 int PrintCombinations(int num, const vector<int> &primes, int from, vector<int> &numbers)
31 {
32 if (num == 0)
33 {
34 cout << "Found: ";
35 copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, " "));
36 cout << '\n';
37 return 1;
38 }
39
40 int count = 0;
41
42 // Search from the from prime to avoid multiple combinations of output isomorphism
43 int primesNum = primes.size();
44 for (int i = from; i < primesNum; ++i)
45 {
46 if (num < primes[i])
47 break;
48 numbers.push_back(primes[i]);
49 count += PrintCombinations(num - primes[i], primes, i, numbers);
50 numbers.pop_back();
51 }
52
53 return count;
54 }
55
56 // Calculate all primes and decompositions of num
57 int ExpandedGoldbach(int num)
58 {
59 if (num <= 3)
60 return 0;
61
62 vector<int> primes;
63 CalcPrimes(num, primes);
64
65 vector<int> numbers;
66 return PrintCombinations(num, primes, 0, numbers);
67 }
68
69 int main()
70 {
71 for (int i = 1; i <= 20; ++i)
72 {
73 cout << "When i = " << i << ":\n";
74 int count = ExpandedGoldbach(i);
75 cout << "Total: " << count << "\n\n";
76 }
77 }
C language code is as follows:
1 #include<stdio.h>
2 #include<math.h>
3 #include<string.h>
4
5 #define maxNum 1000
6 int primeNum[maxNum]={0},ansArr[maxNum]={0};
7 int indexForPrimeNum,indexForAnsArr;
8
9 int work(int num);//Output all primes and decomposed schemes of num and return the total number of schemes
10 int CalcPrimes(int num);//Calculate all prime numbers (excluding Num) in num, and save the results in primeNum []
11
12 int PrintAns(int num,int from);
13 //The idea of backtracking method: select elements from the from element of primeNum [] to accumulate and construct num.
14 //The construction results are placed in ansArr []. After finding a construction scheme, output the scheme
15 //Total number of schemes finally returned
16
17 int main(int argc, char *argv[])
18 {
19 for (int i = 1; i <= 20; ++i)
20 {
21 printf("When i = %d:\n",i);
22 int count = work(i);
23 printf("Total: %d\n\n",count);
24 }
25 return 0;
26 }
27 //Calculate all prime numbers (excluding Num) in num, and save the results in primeNum [] Returns the number of array elements
28 int CalcPrimes(int num)
29 {
30 int i,j,root,k=0;
31
32 if(num<2) return k;
33 memset(primeNum,0,sizeof(primeNum));
34
35 primeNum[k++]=2;
36 for(i=3;i<num;i++)
37 {
38 root=sqrt(i);
39 for(j=2;j<=root;j++)
40 {
41 if(i%j==0) break;
42 }
43 if(j>root) primeNum[k++]=i;
44 }
45 return k;
46 }
47 //Call PrintAns() to output all primes and decomposed schemes of num, and return the total number of schemes
48 int work(int num)
49 {
50 if(num<=3) return 0;
51
52 indexForPrimeNum=CalcPrimes(num);
53
54 memset(ansArr,0,sizeof(ansArr));
55 indexForAnsArr=0;
56 return PrintAns(num,0);
57 }
58
59 //The idea of backtracking method: select elements from the from element of primeNum [] to accumulate and construct num.
60 //The construction results are placed in ansArr []. After finding a construction scheme, output the scheme
61 //Total number of schemes finally returned
62 int PrintAns(int num,int from)
63 {
64 int i;
65 if(num==0)
66 {
67 printf("Found: ");
68 for(i=0;i<indexForAnsArr;i++) printf(" %d",ansArr[i]);
69 printf("\n");
70 return 1;
71 }
72
73 int totalCount = 0;
74 //Search from the from prime to avoid multiple combinations of output isomorphism
75 for(i=from;i<indexForPrimeNum;i++)
76 {
77 if(num<primeNum[i]) break;
78 ansArr[indexForAnsArr++]=primeNum[i];
79 totalCount+=PrintAns(num-primeNum[i],i);
80 indexForAnsArr--;
81 }
82 return totalCount;
83 }
reference resources:
http://www.cppblog.com/superKiki/archive/2010/05/27/116506.html
http://blog.csdn.net/geniusluzh/article/details/8118683