动态规划——一维dp数组与二维dp数组

动态规划——一维dp数组与二维dp数组

对于二维dp数组，递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

于其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。这就是一维dp数组

动态规划五部曲分析如下：

确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
二维dp数组dp[i][j]，dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

确定dp数组的递推公式

一维dp
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
1
2

二维dp
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
1
2

dp数组初始化

一维dp数组：
dp[0]初始化为0，非零下标，如果“石头”价值存在负数，则初始化为负无穷，如果都是正数，则初始化为0
但其实还有一种情况，dp[0]初始化为1，就是当背包容量为0的时候，放0个物品，有部分题目是允许这种情况的
二维dp数组：
dp[i][0]初始化为0
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最⼤价值
初始化代码如下：

// 倒叙遍历 

for (int j = bagWeight; j >= weight[0]; j--) { 
    dp[0][j] = dp[0][j - weight[0]] + value[0]; // 初始化i为0时候的情况 
}
1
2
3
4
5

数组遍历

一维数组遍历：

//注意：背包容量是从大到小遍历
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

1
2
3
4
5
6
7
8

二维数组遍历：

//物品重量和背包容量都是从小到大
// weight数组的大小 就是物品个数 
for(int i = 1; i < weight.size(); i++) { // 遍历物品 
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量  
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化 
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 
         
    } 
} 
1
2
3
4
5
6
7
8
9

最终结果

一维数组：dp[j]
二维数组：dp[i][j]