程序员必学算法.docx

一维dp数组（滚动数组）： 对于背包问题其实状态都是可以压缩的。在使用二维数组的时候，递推公式：dp[j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value);其实可以发现如果把dp[i - 1]那一层拷贝到dp上，表达式完全可以是：dp[j] = max(dp[j], dp[j - weight] + value);于其把dp[i - 1]这一层拷贝到dp上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。读到这里估计大家都忘了 dp[j]里的i和j表达的是什么了，i是物品，j是背包容量。dp[j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。 一维dp01背包完整C++测试代码： void test_1_wei_bag_problem() { &nBSP; vector weight = {1, 3, 4}; vector value = {15, 20, 30}; int bagWeight = 4; // 初始化 vector dp(bagWeight + 1, 0); for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight] + value); } } cout << dp[bagWeight] << endl; } int main() { test_1_wei_bag_problem(); } 可以看出，一维dp 的01背包，要比二维简洁的多！初始化 和 遍历顺序相对简单了。所以我倾向于使用一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级！在后面背包问题的讲解中，我都直接使用一维dp数组来进行推导。