动态规划 Dynamic Programming

综述

动态规划一般形式就是求最值。比如说求最长递增子序列、最小编辑距离等。
求解动态规划核心问题是穷举。动态规划穷举优点特别，因为这类问题通常存在重叠子问题，通常需要DPTable来优化穷举过程，避免重复计算。
动态规划问题一个具备最优子结构，通过子问题的最值得到原问题的最值。
实际解题过程中，关键是写出正确的状态转义方程。

零钱兑换

零钱兑换

1. 首先找到最优子结构：要凑总数amount，选择硬币coin，保证剩下的amount-coin所需硬币最少。遍历所有的硬币，对所有子问题结果取最小值： ```python sub_res_list = [] for coin in coins: sub_res = dp(coins, amount - coin) if sub_res == -1:

    continue

   sub_res_list.append(sub_res)

return min(sub_res_list) if sub_res_list else -1

2. 确定**停止条件**：如果剩下金额为0，问题解决，不需要凑硬币，返回0；如果剩下金额小于0，当前凑法无解，返回特殊值-1
```python
def dp(coins, amount):
    if amount == 0:
        return 0 # 问题得解
    if amount < 0:
        return -1 # 此路径无解
    ...

1. 消除重叠子问题：总数amount对应的最优解是固定的，使用hashmap等缓存中间结算结果，避免重复计算

   def dp(coins, amount):
    ... # 停止条件
    if amount in cache:
        return cache[amount]
    ... # 状态转移
    cache[amount] = rv
    return rv

   实战

   零钱兑换