一个正整数nn可以表示成若干个正整数之和，形如：n=n1+n2+…+nkn=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n，请你求出n共有多少种不同的划分方法。
共一行，包含一个整数n。
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对109+7109+7取模。
1≤n≤10001≤n≤1000
两种做法
原题目题意就是从 1 ~ n 中选选任意个数 组成 n 也就是说从 1 ~ i 中选任意个数加起来等于j; 所以这个题就为完全背包问题的变式! f[i][j] 的状态表示: i 为 从 1 ~ i 中选 总体积恰好为 j f[i][j] 的性质 : 数量; f[i][j] 的计算: 第i个物品选k个; f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j - i*2] + ....f[i-1][j-i*s]; f[i][j - i] = f[i-1][j-i] + f[i-1][j - i*2] + ....f[i-1][j-i*s]; 合并一下 f[i][j] = f[i-1][j] + f[i][j-i]; 优化成一维 f[j] = f[j] + f[j-i]; #include<iostream> #include<cstring> using namespace std; const int N=100005; typedef long long LL; const LL MOD=1e9+7; LL dp[N]; int main() { int n; scanf("%d",&n); memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { dp[j]=(dp[j]+dp[j-i])%MOD; } } printf("%lld\n",dp[n]); return 0; }最小值为1：就是加进来一个1的方案，所以方案 + 1，总和 +1，例如： i=5 ，j=2（2 3） i=6，j=3(1,2,3) 最小值>1： 将每一个数都减去1，总和就会减去j。
#include<iostream> using namespace std; const int N=1005,MOD=1e9+7; int dp[N][N]; int main() { int n; scanf("%d",&n); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%MOD; } } int ans=0; for(int j=1;j<=n;j++) { ans=(ans+dp[n][j])%MOD; } printf("%d\n",ans); return 0; }在火影忍者的世界里，令敌人捉摸不透是非常关键的。
我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 MM，他影分身的个数最多为 NN，那么制造影分身时有多少种不同的分配方法？
注意：
影分身可以分配0点能量。分配方案不考虑顺序，例如：M=7,N=3M=7,N=3，那么 (2,2,3)(2,2,3) 和 (2,3,2)(2,3,2) 被视为同一种方案。第一行是测试数据的数目 tt。
以下每行均包含二个整数 MM 和 NN，以空格分开。
对输入的每组数据 MM 和 NN，用一行输出分配的方法数。
0≤t≤200≤t≤20, 1≤M,N≤101≤M,N≤10
题目相当于是把n个苹果放m个盘子
IA=lambda:map(int,input().split()) T=int(input()) for _ in range(0,T): n,m=IA() dp=[[0 for j in range(0,m+10)] for i in range(0,n+10)] dp[0][0]=1 for i in range(0,n+1): for j in range(1,m+1): dp[i][j]+=dp[i][j-1] if i>=j: dp[i][j]+=dp[i-j][j] print(dp[n][m])由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。
在这一天，Dzx可以从糖果公司的 NN 件产品中任意选择若干件带回家享用。
糖果公司的 NN 件产品每件都包含数量不同的糖果。
Dzx希望他选择的产品包含的糖果总数是 KK 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。
当然，在满足这一条件的基础上，糖果总数越多越好。
Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。
第一行包含两个整数 NN 和 KK。
以下 NN 行每行 11 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 10000001000000。
符合要求的最多能达到的糖果总数，如果不能达到 KK 的倍数这一要求，输出 00。
1≤N≤1001≤N≤100, 1≤K≤1001≤K≤100,
Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。
IA=lambda:map(int,input().split()) n,m=IA() a=[0 for i in range(0,n+1)] dp=[[-1e18 for j in range(0,m+10)] for i in range(0,n+10)] for i in range(1,n+1): a[i]=int(input()) dp[0][0]=0 for i in range(1,n+1): for j in range(0,m): dp[i][j]=max(dp[i-1][j],dp[i-1][(j+m-a[i]%m)%m]+a[i]) print(dp[n][0])X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。
输出一个整数，表示至少脱落了多少个种子。
输入字符串长度不超过1000
区间dp
从当前样子变成初始状态需要添加叶子的数量 等价于 当前样子变成最大的回文串需要剪去的叶子的数量 即至少脱落多少个种子 等价于 总数量 - 最大回文子序列的长度
状态计算的选择方式和最长公共子序列类似
s=input() n=len(s) dp=[[0 for j in range(0,n+10)] for i in range(0,n+10)] for le in range(1,n+1): for i in range(0,n): j=i+le-1 if j>=n:break if le==1: dp[i][j]=1 else: if s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2 dp[i][j]=max(dp[i][j],dp[i+1][j]) dp[i][j]=max(dp[i][j],dp[i][j-1]) print(n-dp[0][n-1])