• 看代码随想录一直不太理解这两句话

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

为什么是这样？

1
2
3
4
5
6
7
8
// 求组合数
// 外层循环：遍历物品（颜料）
for (int item : items) {
    // 内层循环：遍历背包容量（货架格子）
    for (int j = item; j <= capacity; j++) {
        dp[j] += dp[j - item];
    }
}

第一轮 (拿出红色颜料)：你拿着红色颜料，从头到尾把货架上所有能刷的地方都刷一遍，更新一遍货架的状态。刷完后，你把红色颜料放回去，并且再也不碰它了。

第二轮 (拿出蓝色颜料)：你拿着蓝色颜料，在当前已经有了红色的货架的基础上，再把所有能刷的地方刷一遍。因为你固定了物品的使用顺序。你总是先用完所有可能的红色，再用蓝色，再用绿色。所以，你最终得到的方案里，颜色出现的顺序必然是 (红, 蓝, 绿)，你永远不会得到 (蓝, 红, 绿) 这样的方案。因为它忽略了物品的排列顺序，所以它是在计算组合数。

1
2
3
4
5
6
7
8
9
10
// 求排列数
// 外层循环：遍历背包容量（货架格子）
for (int i = 1; i <= capacity; i++) {
    // 内层循环：遍历物品（颜料）
    for (int item : items) {
        if (i >= item) {
            dp[i] += dp[i - item];
        }
    }
}

这相当于你一个格子一个格子地去填。

第一轮 (填满容量为1的格子)：你问，要填满容量为1的格子，可以用什么颜料？你把所有可用的颜料（红、蓝、绿…）都试一遍，看看谁能填进去。

第二轮 (填满容量为2的格子)：你问，要填满容量为2的格子，可以怎么做？你可以拿出任何一种颜料，比如红色，然后去看容量为2-红色重量的格子之前是怎么被填满的，把那些方案拿过来，最后涂上红色。你也可以拿出蓝色，再去看…

…

为什么这样是求排列？ 因为它在计算每个容量 i 的方案数时，都允许放入任何一个物品。