案例1: 分治算法
分治思想是并行计算的理论基础基础, 只有能被合理拆分并独立计算的任务才能被并行化处理
Karatsuba 算法
归并排序
快速傅里叶变换
案例2: 贪心算法
所谓的贪心策略, 就是在求解问题的每个步骤时都做出当前情况下的局部最优选择. 显然, 使用这种重视局部而忽略整体的策略并不一定能得出全局最优解, 但对于满足贪心选择性质与最优子结构性质的问题来说, 自顶向下的贪心算法往往是最优选的解决方案. 在计算机科学领域, 许多经典问题的解决方案都是基于贪心策略制定的, 例如: 哈夫曼编码、单源最短路径、最小生成树等. 一般来讲, 证明贪心算法能够求解出全局最优解的难度要远高于设计该算法.
满足贪心选择性质是问题能够通过贪心算法求出全局最优解的必要条件之一. 区别于自底向上求解重叠子问题的动态规划算法, 贪心算法通常以自顶向下的方式执行, 以迭代的方式根据事先制定的贪心策略作出一系列贪心选择, 每次迭代都会将当前所求的问题转化为规模更小的子问题. 所谓的贪心选择性质就是指所求问题的全局最优解可以通过对每个子问题做贪心选择而得出.
而隐含了全局最优解和子问题最优解之间递推关系的最优子结构性质, 则是问题能用贪心算法或动态规划求解的另一个必要条件. 贪心算法的自顶向下处理模式恰好避免了动态规划所主要解决的重叠子问题, 也就是说, 显式指定了下一步要求解的子问题的贪心策略天生具有避免重复计算的性质. 这样看来, 贪心算法其实是动态规划的一种特例.
在确定了问题适合使用贪心算法求解之后, 贪心策略的设计就成为了最核心的工作. 贪心策略必须具备无后效性, 即当前状态的决策不会影响后续状态对最优解的选择. 以经典的部分背包问题为例, 题目要求我们向固定容量的背包中放入包含价值和重量两种属性的物品, 物品可以被拆分, 求背包所能承载的最大价值. 不难想出以下三种贪心策略:
- 按最大价值贪心: 贵重的物品优先放入背包, 目标函数增长最快
- 按最小重量贪心: 轻的物品优先放入背包, 尽可能地放入更多物品
- 按最大单位价值贪心: $单位价值=物品价值/物品重量$, 尽可能地放入单价最高的物品
大部分情况下, 贪心策略的制定是符合常识的. 显然在上述问题中, 采用按最大单位价值的贪心策略能够取得最优解. 选择恰当的贪心策略不仅能显著降低编码难度, 还能以更低的时间和空间复杂度解决问题. 例如在跳跃游戏中, 最佳的贪心策略就是记录当前能达到的最远距离:
1
2
3
4
5
6
7
8
9
10
def canJump(self, nums: List[int]) -> bool:
rightmost, n = 0, len(nums)
for i in range(n):
if i <= rightmost:
rightmost = max(rightmost, i+nums[i])
if rightmost >= n-1: return True
# else: break # 可选剪枝
return False
如果当前索引大于目前可达的最远距离, 则说明该索引位置之后的所有位置均不可达, 因此可以直接返回, 但由于分支预测机制的存在, 这种剪枝方式并不一定能提高处理效率. 总的来看, 使用贪心算法解决该问题的时间复杂度为$O(n)$, 空间复杂度为$O(1)$. 更复杂一些的最小跳跃次数问题, 则需要在原有贪心策略的基础上记录每个点能跳到的最远距离, 当索引到达最远距离时则应该增加跳跃次数:
1
2
3
4
5
6
7
8
9
10
11
def jump(self, nums: List[int]) -> int:
n = len(nums)
rightmost = end = step = 0
for i in range(n-1):
if i <= rightmost:
rightmost = max(rightmost, i+nums[i])
if i == end:
end = rightmost
step += 1
return step
贪心算法的另一类应用在于求解满足特定条件的序列, 例如无限次买卖股票问题就等价于求所有的递增子数组. 这个问题的贪心策略也符合常识, 当股票价格大于前一天买入的价格时就卖出股票, 显然这样可以保证收入最大化:
1
2
3
def maxProfit(self, prices: List[int]) -> int:
return sum(max(0, prices[i] - prices[i-1])
for i in range(1, len(prices)))
而与之相似的摆动序列问题也可以转化为求交替出现的递增和递减数对的数量, 其贪心策略的核心在于过滤连续重复出现的相同类型数对:
1
2
3
4
5
6
7
8
9
10
11
def wiggleMaxLength(self, nums: List[int]) -> int:
up, down, n = 1, 1, len(nums)
if n < 2: return n
for i in range(1, n):
if nums[i] > nums[i-1]:
up = down + 1 # 过滤连续重复出现的上升对
elif nums[i] < nums[i-1]:
down = up + 1 # 过滤连续重复出现的下降对
return max(up, down)
然而, 在解决某些问题时, 无论使用何种贪心策略都无法获得最优解. 例如在柠檬水找零问题中, 假如用户支付的钞票面值并非柠檬水售价的倍数, 那么优先找零大面值钞票的贪心策略就会失效. 在这种情况下, 要么重新寻找贪心策略并证明其正确性, 要么使用更复杂但却更通用的动态规划算法, 这显著揭示了贪心算法的局限性.
总的来说, 贪心算法的优势就在于实现简单且时间复杂度和空间复杂度相对较低, 但严苛的应用条件以及繁琐的证明过程限制了其应用范围. 然而, 针对某些求出最优解的代价过于昂贵甚至无法通过图灵机计算模型求解的问题（NP-hard）, 利用贪心算法快速求出近似最优解就显得十分必要了.
案例3: 动态规划
分治算法求解问题时,每次产生的子问题并不总是新问题,有些子问题重复出现,这种性质称为子问题重叠性质。
在动态规划算法中,对于重复出现的子问题,只是在第一次遇到时执行求解过程,然后把求解结果保存在一个表格(可能是高维表格)中,再遇到这个子问题时,直接从表格中引用答案,从而避免重复计算,达到提高效率的目标。
需要提醒的是,子问题重叠性质不是动态规划适用的必要条件,但是如果该性质不满足时,动态规划方法与其他方法相比就不具备优势。
将复杂的原始问题拆分为一系列可独立求解的子问题就是动态规划（Dynamic Programming）的核心思想. 贪心算法过于关心局部最优而忽略了整体,
- 重叠子问题
- 最优子结构
根据图灵机的定义不难看出, 现代计算机中算法的本质是状态转移, 即从 求解动态规划问题的关键在于得出递推方程
动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的, 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法.
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
爬楼梯
折木棍/剪绳子(对比数学优化与策略)
状态转移方程
\begin{equation} dp(i, j) = \max(dp(i - 1, j), dp(i, j - 1)) + grid[i][j] \end{equation}
案例4: 子序列与子串问题
滑动窗口与动态规划