XDOJ 1036解题报告

这一题其实是一道背包问题的变形(完全背包问题)——可以转意为:将重量为1~N的物品放入容量为N的背包,求方案数。

可以得出状态转移方程:d[i][j] = d[i-1][j] + d[i][j-i]

解释为:用前i个数组成j = 用前i-1个数组成j + 用前i个数组成j-i(即没用数字i的组合数+用了数字i的组合数,两者为i,j的组合方案,且互斥)

由转移方程可得填表顺序如下图所示:

XDOJ 1036解题报告

其中,横轴为i,纵轴为j,方向为从上到下,从左到右,之前还要进行基本项的初始化,不难理解,即d[i][0] = 1; d[0][j] = 0;  最后是边界处理,根据题意,填表只需要填j >= i的情况,当d[x][y]中出现x > y时,按d[x][y] = d[y][y]处理。

XDOJ 1036解题报告

上一篇:查看文章的上一篇下一篇的逻辑总结


下一篇:珍爱之礼 美妙感受