背包问题大总结

背包分类：
1，元素不重复使用。（backpack I, II, V）
2，元素重复使用 ：计算多少可能时又分1）不同order对应不同可能情况 2）相同的元素不同order对应一种可能情况。
2 -1) backpack VI
2-2) backpack IV(和coin 2一样)

背包所有问题都开始用二维DP state来表示，i是元素index，j是容量index。dp[i][j]表示给出前i元素和容量是j时，对应的结果。

优化空间，即优化成一维DP state，只保留j容量index。
类型1和2-2）双层for循环，外层是元素index。内存的容量index要从右往左。原因是，一维状态是模拟二维状态，当前的更新是根据上一行的结果来进行，所以从右往左，否则，左边的值先变了，再用来更新右边的值就错了。

类型2-1），双层for循环，外层是容量index，内层是元素index。都从左往右。