AcWing 900. 整数划分(优化问题)
原题链接
简单
算法1
(完全背包法)
状态表示:
f[i][j]表示只从1~i中选,且总和为j的方案数
状态转移方程:
f[i][j] = f[i - 1][j] + f[i][j - i]
优化
f[j] = f[j] + f[j - i]
Java 代码
f[0] = 1;
for (int i = 1; i <= n ; i++) {
for (int j = i; j <= n ; j++){
f[j] = (f[j]+f[j-i]) % mod;
}
}
算法2
(其他状态表示)
状态表示:
f[i][j]表示总个数为i,总和为j的方案数
状态转移方程:
f[i][j] = f[i - 1][j - 1] + f[i][j - i]
优化
f[i - 1][j - 1]:需要倒序
f[i][j - i]:需要正序
矛盾,所以无法优化
Java 代码
f[0][0] = 1;
for (int i = 1; i <= n ; i++) {
for (int j = i; j <= n ; j++)
f[i][j] = (f[i-1][j-1] + f[i][j - i]) % mod;
}
int res = 0;
for (int i = 1; i <= n ; i++) res = (res + f[i][n]) % mod;
总结
1) f[i][j] = f[i - 1][j] + f[i][j - i]
2) f[i][j] = f[i - 1][j - 1] + f[i][j - i]
两个状态转移方程非常相似,前者能优化,后者却不能优化,并需累加f[i][n]作为答案