算法之动态规划详解
定义
动态规划其实是一种运筹学方法,是在多轮决策过程中寻找最优解的方法。
应用场景
动态规划问题的一般形式就是求最值
。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。
核心思想
求解动态规划的核心求解思路是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。但是我们在求解过程中, 需要避免重复计算从而更快速的找到答案 。
动态规划三要素
- 最优子结构:原问题的最优解所包含的子问题的解也是最优的,通过子问题的最值得到原问题的最值。
- 存在重叠子问题:子问题间不独立(这是动态规划区别于分治的最大不同);如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「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]