整数划分问题

问题1:将正整数n划分成k个正整数之和的方案数, 1,2和2、1只算一次。

f[i][j]表示i划分成j个正整数之和的方案数。

非法情况:

i = 0 或者 j = 0 或者 j > i 时,f[i][j]=0

边界情况:

j = i 或者 j = 1 时,f[i][j]=1

状态转移

j个数中存在1的情况,f[i][j]=f[i-1][j]

j个数中不存在1的情况,f[i][j]=f[i-j][j],分解的j个数先都减去一个1,这样使得最后分解出的数中不包含1。

综上:f[i][j] = f[i-j][j]+f[i-1][j-1]

问题二:求n的划分数 。
f[n][k],k=1,..,n求和。

问题三:n划分成不超过m的方案数
当m=1 或者 n = 1 时, f[n][m] = 1
当m >= n 时,f[n][m]=f[n][n]
f[n][n] = f[n][n-1] + 1 , 包含和不包含n的两种情况
当 m < n 时, f[n][m] = f[n-m][m] + f[n][m-1], 包含和不包含m的两种情况

原文地址:https://www.cnblogs.com/lixyuan/p/13797441.html