于 2019-08-06 20:30:15 发布 · 3.4k 阅读动态规划本就是一个记录再利用的高效算法，由于其要记录之前的状态，必然会使用大量空间，要优化动态规划算法的空间，我们必然要合理利用dp数组，有一种优化方法就是利用滚动数组来进行状态转移。
我们拿动态规划中一个典型例子01背包来举例
问题描述：
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
当我们不进行优化的时候，我们可以定义如下所示的最优子结构
dp[i][j] 表示把前i件恰放入容量为j的背包中的最大价值
c
运行
转移过程如下：
for(int i = 1; i <= n; ++i) { for(int j = 0; j <= W; ++j) { if(j < w[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp
c
运行
