算法之动态规划详解
定义
动态规划其实是一种运筹学方法，是在多轮决策过程中寻找最优解的方法。
应用场景
动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
核心思想
求解动态规划的核心求解思路是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。但是我们在求解过程中， 需要避免重复计算从而更快速的找到答案 。
动态规划三要素
- 最优子结构：原问题的最优解所包含的子问题的解也是最优的，通过子问题的最值得到原问题的最值。
- 存在重叠子问题：子问题间不独立（这是动态规划区别于分治的最大不同）；如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
- 无后效性：即后续的计算结果不会影响当前结果。
动态规划通用解题过程
动态规划没有标准的解题方法，即没有一个完全通用的解题方法。但在宏观上有通用的方法论：
下面的 k 表示多轮决策的第 k 轮：
- 问题分解，将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段。
- 找状态，选择合适的状态变量 S(k)。它需要具备描述多轮决策过程的演变，更像是决策可能的结果。
- 做决策，确定决策变量 u(k)。每一轮的决策就是每一轮可能的决策动作，即当前可以有哪些决策可以选择。
- 状态转移方程。这个步骤是动态规划最重要的核心，即 S(k+1)= uk(sk) 。
- 定目标。写出代表多轮决策目标的指标函数 V(k,n)，即最终需要达到的目标。
- 寻找目标的终止条件。
动态规划的解题核心就是找到状态转移方程，其实所谓的状态转移方程说白了就是数学上的递推方程，没有什么高大上的。就是通过最基础的问题，一步步递推出所需要的最终目标结果。只是在定义状态转移方程的含义时，有不同的定义方式，不同的定义方式会有不同的递推方程式，但是只要定义正确，都可以得到最终正确的结果。
通常状态转移方程定义过程
- 明确当前可改变的
状态有什么；
- 定义dp数组或者递归函数的具体含义；
- 明确每一步可以进行的
选择有哪些；
- 编写递推方程，也就是状态转移方程；
- 明确baseline，也就是递推开始时的基础值是什么。
动态规划解题方式
动态规划的解题方式通常分为两种：
- 通过定义递归方程解决，这是一种自顶向下的求解方式，通常这种方式会有很多重复计算过程，因此可以通过建立备忘录记录中间过程来进行优化；
- 通过定义DP(Dynamic Programming)数组来求解，这是一种自底向上的求解方式。
至于选择哪一种解题方式，可以根据自己的习惯来。自己比较习惯那种方式思考就用哪种方式即可。
简单举例
下面以常见的斐波拉契数列为例来说明一下上述两种求解方式。
斐波那契数列（Fibonacci sequence）是指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……。即后一个数为前两个数之和。在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
通过暴力递归求解
定义fib(n)函数返回的是斐波拉契数列第n项的值：
def fib(n): if n <= 2: return 1 return fib(n-1) + fib(n-2)
此时的时间复杂度O(2^n)指数级，计算很慢。
我们来看一下递归的状态树：
从状态树我们可以看到有很多重复计算的节点，为了避免重复，我们可以通过建立一个备忘录memo记录,来记录中间节点的计算结果，避免重复计算，可以将时间复杂度直接降为O(n)线性复杂度，优化代码如下：
def fib(n): def helper(n): if n <= 2: return 1 # 如果n的值已经计算过，则直接返回值memo[n] if n in memo: return memo[n] memo[n] = fib(n-1) + fib(n-2) return memo[n] memo = {} # 备忘录，记录已经计算过的值，防止重复计算 return helper(n)
以fib(6)为例，递归的求解过程如下：
DP数组的迭代解法
上述递归过程是自顶向下求解的，也就是从目标值逐步向下 层递归，直至达到递归的终止条件，然后将值逐层返回；dp数组则是自底向上求解的，即从最开始的基础出发，然后逐步向上递推至目标值，由于DP数组自身存储了所有的计算过程，因此不存在重复计算。DP的解法如下：
def fib(n): dp = [0 for _ in range(n+1)] # 基础值，也就是baseline dp[1] = dp[2] = 1 for i in range(3, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]
根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
def fib(n): if n <= 2: return 1 prev = 1 curr = 1 for i in range(3,n+1): prev, curr = curr, prev + curr return curr
零钱兑换问题
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的.
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
由于硬币coins是可以无限用的，因此该题唯一可变的状态为总金额amount。因此定义dp[n]表示:要凑出总金额为n，所需的最少硬币数为dp[n]。
状态转移方程为：
# 伪码框架 def coinChange(coins: List[int], amount: int): # 定义：要凑出金额 n，至少要 dp(n) 个硬币 def dp(n): # 做选择，选择需要硬币最少的那个结果 for coin in coins: res = min(res, 1 + dp(n - coin)) return res # 我们要求的问题是 dp(amount) return dp(amount)
递归暴力解法
def coinChange(coins, amount): def dp(n): # 函数定义为目标金额为n时，所需的最少硬币数量 # base case # 目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1 if n == 0: return 0 if n < 0: return -1 # 求最小值，所以初始化结果为正无穷 res = float('inf') for coin in coins: subpro = dp(n-coin) if subpro == -1: # 子问题无解，跳过 continue res = min(res, 1 + subpro) return res if res != float('inf') else -1 return dp(amount)
为了去除重复的计算，我们使用备忘录进行优化：
带备忘录的递归
def coinChange(coins, amount): def dp(n): # 函数定义为目标金额为n时，所需的最少硬币数量 # base case # 目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1 if n == 0: return 0 if n < 0: return -1 if n in memo: return memo[n] # 求最小值，所以初始化结果为正无穷 res = float('inf') for coin in coins: subpro = dp(n-coin) if subpro == -1: # 子问题无解，跳过 continue res = min(res, 1 + subpro) memo[n] = res if res != float('inf') else -1 return memo[n] memo = {} return dp(amount)
DP数组迭代解法
dp[i] = x 表示，当目标金额为i时，至少需要x枚硬币 。
def coinChange(coins, amount): # 数组大小为 amount + 1，初始值也为 amount + 1 # 因为总的零钱个数不会超过amount,所以初始化amount + 1即可 dp = [amount + 1 for _ in (amount + 1)] dp[0] = 0 for i in range(len(dp)): # 内层 for循环，求解的是所有子问题 + 1 的最小值 for coin in coins: # 子问题无解，跳过 if i - coin < 0: continue dp[i] = min(dp[i],1+dp[i-coin]) if dp[amount] == amount + 1: return -1 else: return dp[amount]
