X. https://blog.csdn.net/u010982765/article/details/79044613
01背包问题内层循环必须是逆序的解释
https://www.jiuzhang.com/qa/4313/
有重复背包即完全背包，每个物品都有无限的可重复性，所以当前的结果要从之前已经出现过当前物品的子结果中得到。
所以循环的方向要反一下，一个从下到上，一个从上到下。
X. 完全背包的顺序
https://blog.csdn.net/bujuan827/article/details/52176137
在这种情况下只能采用方式一，把对n的历遍放到第一层循环，这样才能避免把[1,5]、[5,1]算作两条路径。因为你限制了1,5的顺序，
到了i=5之后不可能在发生5,1的情况产生。
对于方式二，把对n的历遍放在第二层，对于任意的一个状态v,都可能历遍每一种硬币，会导致重复冗余的问题。
如果想加深理解，建议最好把两种方式都实现一下，单步执行查看
https://www.jiuzhang.com/qa/2863/
01背包问题内层循环必须是逆序的解释
有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
(01背包中这些物品每种都只有1个，每个物品只能装一次)
基本问题
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：f[i][v]=max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：
“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，
那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，
此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i] 即f[i-1][v-c[i]]+w[i]。
为什么逆序
逆序的关键就在于这个状态转移方程
f[i][v]只与f[i-1][v]和f[i-1][v-C[i]]有关，即只和i-1时刻状态有关，所以我们只需要用一维数组f[]来保存i-1时的状态f[]。
假设i-1时刻的f[]为{a0，a1，a2，…，av}，那么i时刻的f[]中第v个应该为max(av,av-C[i]+W[i])即max(f[v],f[v-C[i]]+W[i])，
这就需要我们遍历V时逆序遍历，这样才能保证求i时刻f[v]时f[v-C[i]]是i-1时刻的值。如果正序遍历则当求f[v]时
其前面的f[0],f[1]，…，f[v-1]都已经改变过，里面存的都不是i-1时刻的值，这样求f[v]时利用f[v-C[i]]必定是错的值。最后f[V]即为最大价值。
数组遍历有时候必须逆序大多是这个原因
我没有想明白，为什么有重复的时候i是从coin开始算到s，而没有重复的时候i是从s开始算到coin？
/**
* @return number of ways to make sum s using repeated coins
*/
public static int coinrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int coin : coins)
for (int i = coin; i <= s; i++)
dp[i] += dp[i - coin];
return dp[s];
}
/**
* @return number of ways to make sum s using non-repeated coins
*/
public static int coinnonrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int coin : coins)
for (int i = s; i >= coin; i--)
dp[i] += dp[i - coin];
return dp[s];
}有重复背包即完全背包，每个物品都有无限的可重复性，所以当前的结果要从之前已经出现过当前物品的子结果中得到。
所以循环的方向要反一下，一个从下到上，一个从上到下。
X. 完全背包的顺序
https://blog.csdn.net/bujuan827/article/details/52176137
在这种情况下只能采用方式一，把对n的历遍放到第一层循环，这样才能避免把[1,5]、[5,1]算作两条路径。因为你限制了1,5的顺序，
到了i=5之后不可能在发生5,1的情况产生。
对于方式二，把对n的历遍放在第二层，对于任意的一个状态v,都可能历遍每一种硬币，会导致重复冗余的问题。
如果想加深理解，建议最好把两种方式都实现一下，单步执行查看
https://www.jiuzhang.com/qa/2863/
首先2维的状态是一个完整的状态，能表示状态详细的信息，为什么会有变成1维，实际上是在2维的前提下，优化了空间复杂度。
本质来说，
本质来说，
f[i][*] 只和 f[i - 1][*] 有关，这给我了我们优化空间复杂度的契机，所有可以优化到一维。（又因为物品是取一个还是可以无限取，那么在一维状态的时候就要仔细考虑如何枚举状态的顺序）。
接下来是关于状态顺序的枚举。就是顺序是怎么思考的。
动态规划问题枚举的顺序只有一个
动态规划问题枚举的顺序只有一个
原则：如果b状态的计算依赖于a状态，那么a状态必须在b状态之前被枚举和计算
k sum 问题也是如此。仔细看转移方程：
所以i需要从小到大枚举，j和t 也是如此。比如这里 你交换i和j的顺序，并没有剖坏我们的原则，则也是正确的，如下：
f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];所以i需要从小到大枚举，j和t 也是如此。比如这里 你交换i和j的顺序，并没有剖坏我们的原则，则也是正确的，如下：
public int kSum(int A[], int k, int target) {
int n = A.length;
int[][][] f = new int[n + 1][k + 1][target + 1];
for (int i = 0; i < n + 1; i++) {
f[i][0][0] = 1;
}
for (int j = 1; j <= k; j++) {
for (int i = j; i <= n; i++) {
for (int t = 1; t <= target; t++) {
f[i][j][t] = 0;
if (t >= A[i - 1]) {
f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
}
f[i][j][t] += f[i - 1][j][t];
} // for t
} // for j
} // for i
return f[n][k][target];
}
不同的顺序算一种方案，先for物品，再for容量，表示前i个物品用了容量j的价值。这样就没有考虑到顺序对答案的影响。
不同的顺序算多种方案，先for容量，再for物品，表示前j的容量，用了前i个物品的价值，这样就相当于当我用了j的容量，前面1->i-1的物品顺序已经确定了，方案数为dp[j]，那么再进行转移，这样就考虑了物品的顺序。
不同的顺序算多种方案，先for容量，再for物品，表示前j的容量，用了前i个物品的价值，这样就相当于当我用了j的容量，前面1->i-1的物品顺序已经确定了，方案数为dp[j]，那么再进行转移，这样就考虑了物品的顺序。
以后遇到这样的问题，要仔细分析一下状态的转移方程，哪些该转移，哪些不该转移，分析清楚了，做法自然就出来了。
