========
动态规划
========

.. default-role:: code

:date: 2021-05-18

.. contents::
   :local:

排列组合问题
=================

参考：

- `5分钟彻底了解排列组合 - 知乎 <https://zhuanlan.zhihu.com/p/41855459>`_
- https://www.zhihu.com/question/450108393/answer/1788658078

顺序的有关与无关。

排列
   - 公式  `m!/(m-n)!`
   - 全排列 = `n!`
   - 排列数 `组合数 * 全排列`

组合
   - 公式 `m!/n!(m-n)!`
   - 「全组合」= 1
   - 组合数 `排列数 / 全排列`

概念 [#]_
=========

1. 抽象问题 - 清晰的可枚举的问题
2. 寻找可以利用的重复计算
3. 重复计算定义为子问题
4. 定义重复子问题之间的关系


.. topic:: 和贪心的区别？

   贪心的子问题是独立的，可不带 context 求解的

背包九讲 [#]_
=============

.. _01-pack:

01 背包问题
~~~~~~~~~~~

问题抽象
^^^^^^^^

`F[i, v]` 为前 i 件物品放入容量为 v 的背包时的最大价值，即此时的 `[0, i]` 的物品都做出了 *未知但正确* 的选择，面对「放不放 i」这个问题，选择的方式是 ::

   F[i, v] = max(F[i-1, v-Ci] + Wi, F[i-1, v])

第一眼会有 「明显是放 i 价值更大啊，放了总是多出 `Wi` 来」的错觉 ，注意： *问题不是线性求解的* ，`F` 是个矩阵而不是数组， *`F[i, v]` 和 `F[i-1, v]` 都是把背包放满了的最优解，并且选择方式可能完全不一致*

.. note:: 比较感慨的是大学时期理解得很费劲的东西，现在看上去并不可怕

从思路到伪代码::

   F[0, 0..V ] <- 0
   for i <- 1 to N
      for v <- Ci to V
         // 从「刚好放满」膨胀到题设的容量 V
         F[i, v] <- max(F[i-1, v], F[i-1, v-Ci] + Wi)

空间复杂度
^^^^^^^^^^

在 1 to N 的循环里，`F[i, v] <- max(F[i-1, v], F[i-1, v-Ci] + Wi)` 说明 `F[i, v]` 只依赖上一次循环（`i-1`）的结果，所以只需要存 `F[i-1, Ci-1..V]` 而不是矩阵 `F[0..N, 0..V]`::

   // WARNING:: 错误的伪代码
   F[0..V] <- 0
   for i <- 1 to N
      for v <- Ci to V
         F[v] <- max(F[v], F[v-Ci] + Wi)

但这么写会发现原来是 `F[i, v]` 的值会在计算中覆盖 `F[i-1, v]` 的值（合并成一个数组了），`V..0` 倒着算就不会有问题了::

   F[0..V] <- 0
   for i <- 1 to N
      for v <- V to Ci
         F[v] <- max(F[v], F[v-Ci] + Wi)

恰好放满背包
^^^^^^^^^^^^

原始问题仅要求了「价值最大」， 当挑选第一个物品时 `F[1, v] = max(F[0, v-Ci] + Wi, F[0, v])` 是可以选择 `F[0, v]` 且 `v!=0` 的，此时背包出现了空隙。

若要求恰好把背包放满，让其无法选 `F[0,1..v]` 即可::

   F[0] <- 0
   F[1..V] <- -∞

.. note:: 当然这样的话可能出现无解的情况

`Ci..V` 的常数优化
^^^^^^^^^^^^^^^^^^

:'( 不想看算了吧。

参考
====

.. [#] https://www.zhihu.com/question/39948290/answer/612439961
.. [#] https://raw.githubusercontent.com/tianyicui/pack/master/V2.pdf