动态规划与背包问题

LeetCode 2021.6.6-2021.6.12 每日一题

动态规划

动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。通常用来求解最优化问题。

大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

通常按照以下4个步骤来设计一个动态规划算法：

刻画一个最优解的结构特征。
递归地定义最优解的值。
计算最优解的值，通常采用自底向上的方法。
采用计算出的信息构造一个最优解。

如果仅仅需要最优解的值，第4步可以忽略。

以求解斐波那契数列第 $n$ 项为例，采用递归求解 $Fib(6)$ 时有以下递归调用树：

fib(6)

而使用动态规划求解同一个问题：

fib_dp

背包问题

01背包问题

问题：有 $N$ 物品和一个容量为 $V$ 的背包。第 $i$ 件物品的重量是 $w_i$ ，价值是 $v_i$ ，每个物品只有一件。求解将哪些物品装入背包可使价值总和最大。

定义一个数组 $dp$，$ dp[i][j],\ (1 \le i \le N,\ )$表示前 $i$ 种物品在背包容量为 $j$ 的时候最优解的值。

对于 $ dp[i][j]$ 来说

如果容量 $j$ 小于当前物品的重量，那么就不能选择第 $i$ 个物品了，此时有$dp[i][j] = dp[i-1][j]$；
如果容量 $j$ 大于等于当前物品的重量，那么可以选择第 $i$ 个物品。此时有 $dp[i][j] = max(dp[i - 1][j],\ dp[i - 1][j - v[i]] + v[i])$ ；

得到状态转移方程： $$ dp[i][j] = \begin{cases} dp[i - 1][j], & \text{ j $\lt$ v[i]} \\ max(dp[i - 1][j],\ dp[i - 1][j - v[i]] + v[i]) & \text { j $\ge$ v[i]} \end{cases} $$

假设背包的容量为 $10$ ，物品的重量和价值如下：

物品编号	1	2	3	4	5
重量wi	2	2	6	5	4
价值vi	6	3	5	4	6

那么，$dp$ 的状态更新完成后的结果就是：

物品数/背包容量	2	3	4	5	6	7	8	9	10
1	6	6	6	6	6	6	6	6	6
2	6	6	9	9	9	9	9	9	9
3	6	6	9	9	9	9	11	11	14
4	6	6	9	9	9	10	11	13	14
5	6	6	9	9	12	12	15	15	15

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


function _01backpack(weights, values, volume) {
  const len = weights.length;
  const dp = new Array(len)
    .fill(0)
    .map((item) => new Array(volume + 1).fill(0));

  for (let i = 0; i < volume; i++) {
    dp[0][i] = i < weights[0] ? 0 : values[0];
  }

  for (let i = 1; i < len; i++) {
    for (let j = 0; j <= volume; j++) {
      if (j >= weights[i]) {
        dp[i][j] = Math.max(
          dp[i - 1][j],
          dp[i - 1][j - weights[i]] + values[i]
        );
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[len - 1][volume];
}

假设下表为 $dp[i][j]$ ，因为$dp[i][-]$ 只依赖于 $dp[i-1][-]$，所以采用滚动数组的方式，去掉 $dp$ 的第一个维度。如果这样做的话，内层循环需要采用倒序遍历，以保证 $dp[i][-]$ 是从 $dp[i-1][-]$ 转移来的。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


function _01backpack2(weights, values, volume) {
  const dp = new Array(volume + 1).fill(0);
  const len = weights.length;

  for (let i = 0; i < len; i++) {
    for (let j = volume; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[volume];
}

完全背包问题

问题：有无数件物品和一个容量为 V 的背包。第 i 件物品的重量是wi，价值是vi 。求解将哪些物品装入背包可使价值总和最大。

同样定义数组 $dp$ ，$ dp[i][j]$表示前 $i$ 种物品在背包容量为 $j$ 的时候最优解的值。

对于 $ dp[i][j]$ 来说

如果容量 $j$ 小于当前物品的重量，那么就不能选择第 $i$ 个物品了，此时有$dp[i][j] = dp[i-1][j]$；
如果容量 $j$ 大于等于当前物品的重量，那么可以选择第 $i$ 个物品。因为物品可以重复选择，此时有 $dp[i][j] = max(dp[i - 1][j],\ dp[i][j - v[i]] + v[i])$ ；

状态转移方程： $$ dp[i][j] = \begin{cases} dp[i - 1][j], & \text{ j $\lt$ v[i]} \\ max(dp[i-1][j],\ dp[i][j - v[i]] + v[i]), & \text { j $\ge$ v[i]} \end{cases} $$

同样可以一维化 $dp[i][j]$，去掉第一个维度。此时需要正序遍历，因为 $dp$ 可以在同一维度被刷新。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


function completeBackpack(weights, values, volume) {
  const dp = new Array(volume + 1).fill(0);
  const len = weights.length;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j <= volume; j++) {
      if (j >= weights[i]) {
        dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
      } else {
        dp[j] = dp[j];
      }
    }
  }

  return dp[volume];
}

LeetCode题解

6.06 一和零

题解：

如果把字符串想象成是一个价值为 $1$ 的物品，那么这个问题几乎等价于01背包问题。不同的是，背包有两个容量，分别是字符 ‘0’ 的个数和字符 ‘1’ 的个数。
定义一个三维数组 $dp$，$dp[i][j][k]$ 表示在前 $i$ 个字符串中，最多有 $j$ 个 ‘0’ 和 $k$ 个 ‘1’ 的容量时可以得到的最大字符串数量。字符串的长度为 $l$，最终解就是 $dp[l][m][n]$。
当 $i=0$ 时，没有字符串可用。所以动态规划的边界条件是 $dp[i][j][k] = 0 ,$ ($0\le j \le m,\ 0 \le k \le n$)
$zeros$ 和 $ones$ 分别表示第 $i$ 个字符串中 ‘0’ 和 ‘1’ 的个数。
- 如果 $j \lt zeros$ 或 $ k \lt ones$，那么不能选第 $i$ 个字符串，$dp[i][j][k] = dp[i-1][j][k]$；
- 如果 $j \ge zeros$ 且 $ k \ge ones$ ：
  - 不选第 $i$ 个字符串，有$dp[i][j][k] = dp[i-1][j][k]$；
  - 选择第 $i$ 个字符串，有 $dp[i][j][k] = dp[i-1][j-zeros][k-ones] + 1$；
状态转移方程：
- $A = dp[i-1][j][k]$
- $B = dp[i-1][j-zeros][k-ones] + 1$

$$ dp[i][j][k] = \begin{cases} dp[i - 1][j][k],&\text {$j \lt zeros\ 或\ k < ones$} \\ max(A,\ B), & \text { $ j \ge zeros\ 且\ k \ge ones$} \end{cases} $$

优化：由于 $dp[i][-][-]$ 只依赖于 $dp[i-1][-][-]$ ，所以采用滚动数组的方式，去掉 $dp$ 的第一个维度。
代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


// 获取字符串中'0'和'1'的个数
function getZerosOnes (str) {
  const result = new Array(2).fill(0)
  for (let i = 0; i < str.length; i++) {
    result[str[i].charCodeAt() - '0'.charCodeAt()]++
  }
  return result
}

function findMaxForm(str, m, n) {
  const dp = new Array(m + 1).fill(0).map(()=> new Array(n + 1).fill(0))
  const len = str.length

  for (let i = 0; i < len; i++) {
    const [zeros, ones] = getZerosOnes(str[i])
    for (let j = m; j >= zeros; j--) {
      for (let k = n; k >= ones; k--) {
        dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1)
      }
    }
  }

  return dp[m][n]
}

6.07 目标和

题解：

记数组的元素和为 $sum$，符合题意的方案中被减的数之和为 $neg$，则被加上的数之和为 $sum - neg$。

有以下表达式： $$ (sum - neg) - neg = target $$ 那么， $$ neg = {sum - target\over 2} $$ 因为数组中的元素都是非负整数，那么 $sum$ 和 $neg$ 都是非负整数，上面的等式成立条件是 $sum-target$ 是一个非负偶数。不满足该条件就直接返回 0。
数组中的每个元素都必须选择，通过上面的等式，可以把问题转换成在数组中选择若干个元素，使得这些元素之和等于 $neg$，求可选取方案的最多个数。即背包容量为 $neg$ ，物品价值为均为1的01背包问题。
定义二维数组 $dp$ , 其中 $dp[i][j]$ 表示在数组的前 $i$ 个元素中选取元素，使得元素之和等于 $j$ 的方案数。

数组的长度为 $n$ ，最终解为 $dp[n][neg]$。
当数组中没有元素时，对应只有一个方案。所以动态规划的边界条件是： $$ dp[0][j] = \begin{cases} 1,&\text {$j = 0 $} \\ 0,&\text {$j \ge1$} \end{cases} $$
遍历数组 $nums$ 中的元素，对于 $nums[i] \ (1\le i \le n)$，有
- 如果 $j < nums[i]$ ，则不能选 $nums[i]$，$dp[i][j]=dp[i-1][j]$;
- 如果 $j \ge nums[i]$，那么：
  - 不选择 $nums[i]$，方案数为 $dp[i-1][j]$；
  - 选择 $nums[i]$，方案数为 $dp[i-1][j-nums[i]]$ ；
    
    方案总数 $dp[i][j] = dp[i-1][j] + dp[i-1][j-sums[i]]$
状态转移方程： $$ dp[i][j] = \begin{cases} dp[i-1][j],& \text{$j < sums[i] $}\\ dp[i-1][j] + dp[i-1][j-sums[i]],&\text{$j\ge sums[i]$}\ \end{cases} $$

省略第一个维度的代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


function findTargetSumWays(nums, target) {
  let sum = nums.reduce((a, b) => a + b, 0);

  const gap = sum - target;

  //  sum-target是一个非负偶数，直接返回 0
  if (gap < 0 || gap % 2 !== 0) {
    return 0;
  }

  const negative = Math.floor(gap / 2);
  const dp = new Array(negative + 1).fill(0);
  dp[0] = 1;

  for (const num of nums) {
    for (let j = negative; j >= num; j--) {
      dp[j] += dp[j - num];
    }
  }

  return dp[neg];	
}

6.08 最后一块石头的重量

题解：

问题等价于把石头分为两堆，求两堆石头的最小差值。假设石头总重量为 $sum$，问题可转换为背包容量为$\lfloor{sum/2}\rfloor$ ，物品的价值为石头的重量，物品的重量为1的01背包问题。
定义数组 $dp[i][j]$ ，表示前 $i$ 块石头中选择若干块，容量为 $j$ 时石头的最大重量。动态规划的边界是 $dp[0][0]=0$ ，假设 $stones$ 数组的长度为 $n$ ，则最终解为 $sum - 2 * dp[n][\lfloor{sum/2}\rfloor]$。
状态转移方程：
- $A = dp[i-1][j]$
- $B = dp[i-1][j-stones[i]]+stones[i]$ $$ dp[i][j]= \begin{cases} dp[i-1][j],& \text{j < stones[i]}\\ max(A,\ B),&\text{$j \ge stones[i]$}\ \end{cases} $$
$dp[i][-]$ 的值只依赖于 $dp[i-1][-]$ ，同样可以去掉第一个维度，内部采用倒序遍历。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


function lastStoneWeight (stones) {
    const sum = stones.reduce((a,b) => a + b, 0)
    const len = Math.floor(sum / 2)
    const dp = new Array(len + 1).fill(0)

    for (let i = 0; i < stones.length; i++) {
        for (let j = len; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
        }
    }

    return sum - 2 * dp[len]	
};

6.09 盈利计划

题解：

问题与01背包很类似，不同的是这里有两种容量，一个是员工人数 $n$，一个是最小利润 $minProfit$。
定义一个三维数组 $dp$ ，$dp[i][j][k]$ 表示前 $i$ 项工作中，选择 $j$ 个员工，并满足最小利润为 $k$ 的方案数。假设员工组数组 $group$ 的长度为 $len$，那么最终答案就是： $$ \sum_{i=1}^ndp[len][i][minProfit] $$
初始状态时方案数为1，所以 $dp[0][0][0]=1$ 。
对于当前工作 $i$，
- 如果不能开展该项工作，那么 $dp[i][j][k] = dp[i-1][j][k] $
- 如果可以开展该项工作，那么当前小组人数为 $group[i]$ ，当前利润数为 $profit[i]$ ，为了保证最小利润，$dp$ 的第三个维度设置为 $max(0, k-profit[i])$ ，所以此时有： $$ dp[i][j][k] = dp[i-1][j-group[i]][max(0,\ k - profit[i])] + dp[i-1][j][k] $$
状态转移方程： $$ dp[i][j][k]= \begin{cases} dp[i-1][j][k],&\text {j < group[i]}\\ dp[i-1][j-group[i]][max(0,\ k - profit[i])] + dp[i-1][j][k],&\text{$j \ge group[i]$}\ \end{cases} $$
该 $dp$ 的省去第一个维度同样可以省略。省略了第一个维度之后，初始状态需要更改，对于任意一个 $minProfit$，总有 $dp[i][0]=1,\ 0 \le i \le n$。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


function profitTableSchemes(n, minProfit, group, profit) {
  const dp = new Array(n + 1)
    .fill(0)
    .map(() => new Array(minProfit + 1).fill(0));

  for (let i = 0; i <= n; i++) {
    dp[i][0] = 1;
  }

  const len = group.length,
    MOD = 1e9 + 7;

  for (let i = 1; i <= len; i++) {
    const employee = group[i],
      earn = profit[i];
    for (let j = n; j >= employee; j--) {
      for (let k = minProfit; k >= 0; k--) {
        dp[j][k] = (dp[j][k] + dp[j - employee][Math.max(0, k - earn)]) % MOD;
      }
    }
  }

  return dp[n][minProfit];
}

6.10 零钱兑换II

题解：

问题类似于完全背包，不同点是该问题求解的是硬币组合种类。定义一个数组 $dp$ ，$dp[i]$ 表示金额等于 $i$ 的硬币组合种类，动态规划的边界条件是 $dp[0]=1$ 。
给定总金额为 $amount$，硬币组合为 $coins$。对于一个面额为 $coin$ 的硬币，当 $coin \le i \le amount$ 时，每存在一种硬币组合的总额为 $i-coin$，就存在一种硬币组合的总额为 $i$ 。
遍历 $coins$，更新 $dp$ 中金额大于等于该面额的元素的值。最后得到答案 $dp[amount]$ 。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


function changeII(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = dp[i] + dp[i - coin];
    }
  }

  return dp[amount];
}

6.11 完全平方数

题解：

与完全背包很相似，每一个平方数就是一个价值为 $1$ 的物品，背包的容量就是正整数 $n$ , 不过这里要使得背包的价值最小。
状态转移方程： $$ dp[i] = min(dp[i],\ dp[i-j*j] + 1) $$

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


function numSquares(n) {
  const dp = new Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    dp[i] = i;
    for (let j = 1; i > j * j; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
}

6.12 数位成本和为目标值的最大数字

题解：

首先，整数位数越多，整数就越大。因此，我们可以先计算出最多的整数位数。求解的问题相当于容量为 $target$ ，物品重量为 $cost[i]$，物品价值均为 $1$ 的完全背包问题。
定义一个数组 $dp$ , 为了方便计数，我们定义 $dp[i+1][j]$ 表示前 $i$ 个数且花费成本等于 $j$ 的最多位数。
为了方便比较，设置 $dp$ 的初始值为 -Number.MAX_SAFE_VALUE，另外 $dp[0][0] = 0$。
状态转移方程： $$ dp[i+1][j]= \begin{cases} dp[i][j],&\text{$j<cost[i]$}\\ max(dp[i][j],\ dp[i+1][j-cost[i]]+1), &\text{$j \ge cost[i]$}\ \end{cases} $$
$dp$ 的第一个维度可以省略。得到最多的整数位数 $dp[target]$ 后，我们需要根据 $ dp$ 来生成最终答案。$dp$ 数组有一个规律是如果 $dp[j]$ 与 $dp[j-cost[i]] + 1$ 时，说明后者是由前者转移过来的。在这个过程里，我们可以倒序遍历 $cost$ 数组，每当满足这个规律时，就把当前的 $i$ 推入数组 $result$ ，遍历完成后把 $result$ 连接成字符串即为最终答案。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


function largestNumber(cost, target) {
  const dp = new Array(target + 1).fill(-Number.MAX_SAFE_INTEGER);
  dp[0] = 0;

  for (const item of cost) {
    for (let i = item; i <= target; i++) {
      dp[i] = Math.max(dp[i], dp[i - item] + 1);
    }
  }

  if (dp[target] < 0) {
    return "0";
  }

  const result = [];

  // 根据dp来生成最大整数
  for (let i = 8, j = target; i >= 0; i--) {
    for (let c = cost[i]; dp[j] === dp[j - c] + 1 && j >= c; j -= c) {
      result.push(String.fromCharCode("1".charCodeAt() + i));
    }
  }

  return result.join('');
}

最后修改于 2021-06-15

物品数/背包容量	2	3	4	5	6	7	8	9	10
1	6	6	6	6	6	6	6	6	6
2	6	6	9	9	9	9	9	9	9
3	6	6	9	9	9	9	11	11	14
4	6	6	9	9	9	10	11	13	14
5	6	6	9	9	12	12	15	15	15

物品数/背包容量	2	3	4	5	6	7	8	9	10
1	6	6	6	6	6	6	6	6	6
2	6	6	9	9	9	9	9	9	9
3	6	6	9	9	9	9	11	11	14
4	6	6	9	9	9	10	11	13	14
5	6	6	9	9	12	12	15	15	15

物品数/背包容量	2	3	4	5	6	7	8	9	10
1	6	6	6	6	6	6	6	6	6
2	6	6	9	9	9	9	9	9	9
3	6	6	9	9	9	9	11	11	14
4	6	6	9	9	9	10	11	13	14
5	6	6	9	9	12	12	15	15	15