51nod 1201 整数划分 基础DP

时间:2023-03-05 09:02:20
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
51nod 1201 整数划分 基础DP 收藏
51nod 1201 整数划分 基础DP 关注
将N分为若干个不同整数的和,有多少种不同的划分方式,例如:n = 6,{6} {1,5} {2,4} {1,2,3},共4种。由于数据较大,输出Mod 10^9 + 7的结果即可。
Input
输入1个数N(1 <= N <= 50000)。
Output
输出划分的数量Mod 10^9 + 7。
Input示例
6
Output示例
4

dp[i][j] 数i 可以有j个不同的数组合的方案数

dp[i][j] = dp[i-j][j] + dp[i-j][j-1]

将i 划分为 j个数,然后j个数都-1

(由于题目限定,n只能由不同的数构成的,所以j个数里面最多有一个1)

前者表示,之前的j个数没有1的存在,所以都-1以后还是j个数

后者表示 ,之前的j个数有1的存在,所以-1以后剩下j-1个数

n最多可以被m个数构成,那么发现最大的m 即

1 + 2 + ... + m = n , (1 + m)*m = n * 2,j只要遍历sqrt(n * 2)个就好了。所以复杂度为n*sqrt(n*2)