前言

在背包问题总结中，提到了：

    如果是0-1背包，即数组中的元素不可重复使用：target层循环倒序；

    如果是完全背包，即数组中的元素可重复使用：target层循环正序；

那么为什么呢？正序和倒序有什么区别呢？

（PS：建议下看一下 01背包问题——二维转一维数组分析，了解一下为什么如何使用一维数组解题，以及为什么使用倒序解01背包问题）

例题

先以题目为例：

问题一：（518. 零钱兑换 II）

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int num : coins) {
        for (int i = num; i <= amount; i++) {
            dp[i] += dp[i - num];
        }
    }
    return dp[amount];
}

问题二：

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币只有1个。

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int num : coins) {
        for (int i = amount; i >=num; i--) {
            dp[i] += dp[i - num];
        }
    }
    return dp[amount];
}

分析

比较上面两个问题，可以发现唯一的区别就是硬币的个数，也即是否能重复使用。

    问题一：是完全背包问题，所以target层循环需要正序；

    问题二：是01背包问题，所以target层循环需要倒序；

而解题上，不管是01背包问题还是完全背包问题，对于dp[i]的计算都是dp[i] += dp[i - num];唯一不同的是：先从target开始计算？还是先从1开始计算？那么从1跟从target有什么区别？

在 01背包问题——二维转一维数组分析一文中，提到了对于01背包问题，要从dp[target]开始计算、开始覆盖，直至dp[1]。在计算dp[i]前，要求dp[i]和dp[i-num]的值都没有变动过，取的值应该是前i-1个数的选取的结果。

也就是说，从target开始计算，dp[i]和dp[i-num]使用的值是前i-1个数的选取的结果；而从1开始计算，dp[i]使用的值是前i-1个数的选取的结果，dp[i-num]使用的值是前i个数的选取的结果；

=》正序：dp[i-num]使用的值是前i个数的选取的结果；倒序：dp[i-num]使用的值是前i-1个数的选取的结果。

=》那么，为什么完全背包问题，dp[i-num]使用的值要是前i个数的选取的结果？01背包问题dp[i-num]使用的值要是前i-1个数的选取的结果？

这个就需要回到完全背包问题和01背包问题的本质区别上来分析了。

方便解释，我们假设f(i,j)为前i个数中选取和为j的组合结果数，那么会有以下结论：（i>=num）

    f(i-1,i-num)表示前i-1个数中选取和为i-num的组合结果数；

    f(i,i-num)表示前i个数中选取和为i-num的组合结果数；

    f(i,i-num) >= f(i-1,i-num)，即f(i,i-num) 在f(i-1,i-num)的组合结果上，又多了使用了第i个数进行组合的结果数。

对于完全背包问题，因为元素可以重复使用，如果dp[i-num]直接使用f(i-1,i-num)的话，那么就少掉了使用第i个数进行组合且和为i-num的结果数，所以需要使用f(i,i-num)。

对于01背包问题，因为元素不重复使用，dp[i-num]的组合结果里不应该存在第i个数。所以应该使用f(i-1,i-num)。

故，对于完全背包问题，dp[i-num]的结果应该再加上使用第i个数进行组合且和为i-num的结果数，也就是target层循环应该使用正序。而对于01背包问题，dp[i-num]的结果不需要再加上使用第i个数进行组合且和为i-num的结果数，也就是target层循环应该使用倒序。