题解

核心算法

外层枚举总长度 c，内层枚举最后一步 x，累加 dp[c-x]。

思路推导

按最后一步分类得到的是有序序列；循环顺序是本题核心。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(nW)
• 空间复杂度：O(W)

易错点

若外层枚举物品会只统计无序组合。

完整标程见 std/main.cpp。