动态规划
[算法导论 第 15 章]
动态规划 (dynamic programming, dp) 中的 programming 是指一种表格法, 而不是编程.
分拆数
求将非负整数 m 拆成 n 个非负整数之和的方法数 (n ≥ 1).
这等于将 m 拆成不超过 n 个正整数之和的方法数.
例如, 将 m 个相同苹果放入 n 个相同篮子.
说明: 5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1
= 2 + 2 + 1 = 2 + 1 + 1 + 1 = 5*1, 共 7 种.
不妨设和式已经按大小排好序:
`m = m_1 + m_2 + cdots + m_n`,
`quad m_1 le m_2 le cdots le m_n`.
若和式中含有 0, 则 `m_1 = 0`, 此时只需将 `m` 拆成 `n-1` 个非负整数之和,
方法数为 `F_(m, n-1)`; 若和式中不含 0, 此时只需将 `m-n` 拆成 `n`
个非负整数之和, 然后给每个数加 1 即可, 方法数为 `F_(m-n, n)`:
`F_(m, n) = {
1, if m = 0 or n = 1;
F_(m, m), if n gt m;
F_(m, n-1) + F_(m-n, n), otherwise
:}`
时间复杂度为 `O(m n)`.
双蛋问题
设有 f (floors) 层楼, e (eggs) 个鸡蛋, 从 `1 le k le f` 层将鸡蛋丢下.
假设存在一个临界楼层 `1 le n le f`, 当 `k lt n` 时鸡蛋不碎,
当 `k ge n` 时鸡蛋破碎. 现在利用手中的鸡蛋做试验, 寻找临界楼层 `n`.
在最坏情况下, 所需的试验次数最少是多少?
从 k 层丢下鸡蛋, 若鸡蛋破碎, 范围缩小到 [1..k-1], 并且鸡蛋数减 1;
若鸡蛋不碎, 范围缩小到 [k+1..f], 鸡蛋数不变.
由于事先不知道鸡蛋是否破碎, 考虑最坏情况, 应取两种情况的最大值.
最后, 关于 k 求最小值, 再加 1 就得到试验的最少次数.
`F_(f, e) = {
f, if e = 1 or f = 1;
1 + min_k max(F_(k-1, e-1), F_(f-k, e)), otherwise
:}`
最大子数组
找出非空数组 nums 中具有最大和的非空子数组 [lo, hi].
说明: 最大子数组是 [4, -1, 2, 1], 和为 6.
用 `f_n` 表示 [0, n] 中最大子数组的元素之和,
`g_n` 表示 [0, n] 中所有以下标 n 为右边界的子数组的最大和.
若最大子数组不含下标 n, 则 `f_n = f_(n-1)`,
否则, `f_n = g_n`.
`f_n = {
"nums"[0], if n = 0;
max(f_(n-1), g_n), otherwise;
:}`
`g_n = {
"nums"[n], if n = 0 or g_(n-1) lt 0;
g_(n-1) + "nums"[n], otherwise;
:}`
背包问题 [算法导论 16.2 节]
有 `n` 件商品, `A_k`, 价值 `v_k`, 重 `w_k`, `k = 0, 1, cdots, n-1`;
有一个容量为 `W` 的背包, 其中 `v_k`, `w_k`, `W` 均为正整数.
-
0-1 背包问题
若每件商品都是不可拆分的 (比如金锭), 要么全部装进背包 (1),
要么不装 (0), 求背包能装下的商品最大总价值.
说明：装入重 20 和 30 的商品, 价值为 100 + 120 = 220.
-
分数背包问题
若商品可以任意拆分 (比如金沙), 情况又如何?
- 按下标顺序依次判断商品是否应进入背包.
假设已判断 `n-k` 件商品, 还有 `k` 件尚待判断, 此时背包剩余容量设为
`w`. 记这时背包能装下的商品最大价值为 `f_(k,w)`, 考虑下一件商品
`A_(n-k)`, 若装下它, 价值变为 `v_(n-k) + f_(k-1,w-w_(n-k))`,
否则价值变为 `f_(k-1,w)`:
`f_(k, w) = {
0, if k = 0 or w = 0;
f_(k-1,w){::}, if w lt w_(n-k);
max(f_(k-1,w), v_(n-k) + f_(k-1,w-w_(n-k))), otherwise;
:}`
最长递增子序列
最优矩阵相乘次序
最优二叉树
贪心算法
Huffman 编码、最小生成树、最短路径问题都是贪心算法的典型应用。