1.hdu 1028 整数划分
首先，我们引进一个小小概念来方便描述吧，dp[n][m]是把自然数划划分成所有元素不大于m的分法，例如： 当n=4，m=1时，要求所有的元素都比m小，所以划分法只有1种：{1，1，1，1}； 当n=4，m=2时，只有3种{1，1，1，1},{2，1，1}，{2，2}； 当n=4，m=3时，只有4种{1，1，1，1},{2，1，1}，{2，2},{3,1}； 当n=4，m=5时，只有5种{1，1，1，1},{2，1，1}，{2，2},{3,1},{4}； 从上面我们可以发现：当n==1||m==1时，只有一种分法; 当n < m时，由于分法不可能出现负数，所以dp[n][m]=dp[n][n]; 当n==m时，那么就得分析是否要分出m这一个数，如果要分那就只有一种{m}，要是不分，那就是把n分成不大于m-1的若干份；即dp[n][n]=1+dp[n][n-1]; 当n>m时，那么就得分析是否要分出m这一个数，如果要分那就{{m},{x1,x2,x3..（可能含有m）}}时n-m的分法dp[n-m][m]，要是不分，那就是把n分成不大于m-1的若干份；即dp[n][n]=dp[n-m][m]+dp[n][m-1];
代码：
#include<iostream> using namespace std; #define maxn 121 int dp[maxn][maxn]={0}; int main() { int i,j; for(i=1;i<=121;i++)dp[1][i]=dp[i][1]=1; for(i=2;i<121;i++) { for(j=2;j<=121;j++) { if(i<j) dp[i][j]=dp[i][i]; else if(i==j)dp[i][j]=1+dp[i][j-1]; else if(i>j) dp[i][j]=dp[i-j][j]+dp[i][j-1]; } } int n; while(scanf("%d",&n)!=EOF)printf("%d\n",dp[n][n]); return 0; }ps：这题也可以母函数做，参考： http://blog.csdn.net/guhaiteng/article/details/52904663
2.CDOJ 1307 ABCDE
题意： 在数电中，有一种码，类似BCD码这种玩意儿 第i位如果为1的话，那么ans+=a[i]，a[i]是这一位的位权 然后现在给你一个n，问你一共有多少种码可以表示1~n的所有数呢？ 1,1,2和2,1,1视作一样。
解法： DP预处理 首先考虑这个东西，如果不视作一样的话，就很简单了
dp[i]表示当前和为i的方案数，显然这个玩意儿能够一直转移到2i-1去。(比如5，你转移到最大的肯定是3，不然就无法表示出1,2,3,4,5每个数了，这很显然)
由于视作一样，那么我们只要维护一个当前的最大值就好了，保证这个序列是递增的，这样就都不会一样了。
dp[i][j]表示现在和为i，最大值为j的方案数有多少。
转移方程: dp[i][j]=(dp[i−1][j−1]+dp[i−j][j]）
前者表示由没有最大值j转移过来，后者表示从有最大值j转移过来
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 1e9+7; long long dp[5010][5010]; long long ans[5010]; int main() { dp[0][0] = 1; for(int i = 1; i <= 5000; i++){ for(int j = 1; j <= (i+1)/2; j++){ dp[i][j] = (dp[i-1][j-1]+dp[i-j][j])%mod; ans[i] += dp[i][j]; ans[i] %= mod; } } int T; scanf("%d", &T); while(T--){ int n; scanf("%d", &n); printf("%lld\n", ans[n]); } return 0; }3.687C The values you can make 题意：给n个各有价值的硬币，要从它们中选出若干个组合成面值k，而要求的是各个方案里这些选出的硬币能组合出来的面值有哪些
dp[i][j][k]表示到第i个硬币，和为j，组成面值为k这种情况是否存在。 要用滚动数组写，不然要爆内存
详细可以看题解： http://codeforces.com/blog/entry/45770
代码：
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back #define ll long long #define mod 1000000007 #define ull unsigned long long #define mst(ss,b) memset(ss,b,sizeof(ss)); #define pl(x) cout << #x << "= " << x << endl; const int inf=0x3f3f3f3f; const int N=505; bool dp[2][N][N];//第i个 和为j 组成面额为k int n, k, c[N], cnt; int ans[N]; int main(){ scanf("%d%d", &n, &k); for(int i=1; i<=n; i++)scanf("%d", &c[i]); dp[0][0][0] = 1; for(int i=1; i<=n; i++){ for(int j=k; j>=0; j--){ for(int x=j; x>=0; x--){ dp[i%2][j][x] |= dp[(i-1)%2][j][x]; if(j-c[i] >= x)dp[i%2][j][x] |= dp[(i-1)%2][j-c[i]][x]; if(x >= c[i])dp[i%2][j][x] |= dp[(i-1)%2][j-c[i]][x-c[i]]; } } } for(int i=0; i<=k; i++){ if(dp[n%2][k][i])ans[++cnt] = i; } printf("%d\n", cnt); for(int i=1; i<=cnt; i++)printf("%d ", ans[i]); return 0; }4.51nod 1201 整数划分
思路： dp[i][j]表示i这个数划分成j个数的情况数。 dp[i][j] = dp[i - j][j] + dp[i - j][j - 1] 前者表示将i - 1划分为j个数，然后j个数都+1 还是不重复 后者表示将i - 1划分为j - 1个数，然后j - 1个数都+1，再加上1这个数 普通的dp是O(n^2)的，但是可以发现1 + 2 + … + m = n ， (1 + m)m = n 2，j只要遍历sqrt(n * 2)个就好了。所以复杂度为O(n*sqrt(n*2))
#include <bits/stdc++.h> using namespace std; #define mod 1000000007 template<class T> void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar()); for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar()); F && (num=-num); } const int N=5e4+10; int dp[N][351], n; int main(){ read(n); dp[0][0] = 1; for(int i = 1; i < 350 ; i++){//i个数 for(int j = 0; j <= n ; j++){//组成j if(j - i >= 0){ dp[j][i] = (dp[j - i][i] + dp[j - i][i - 1]) % mod; } } } int ans = 0; for(int i = 1; i < 350; i++) ans = (ans + dp[n][i]) % mod; printf("%d\n", ans); return 0; }未完待续。。。。
