基本概念

动态规划(dynamic programming)是运筹学的一个分支，是求解多阶段决策过程(decision process)最优化的数学方法。

动态规划过程：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列是在变化的状态中产生，这种多阶段最优化策略解决问题的过程称为动态规划。

基本思想

基本思想与分治法类似，都是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

动态规划和分治的区别： 适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

适用情况

满足以下三个性质：

  1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
  2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。
  3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

求解步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

  • 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
  • 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
  • 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

算法实现

  1. 定义状态函数：dp[i]dp[i], 数组保存子问题解，维数根据问题而定。
  2. 状态转移方程：dp[i]=best(dp[i−1],dp[i−2],...)dp[i]=best(dp[i-1], dp[i-2], ...)
  3. 最优子结构。
  4. 递归+记忆化。

示例

斐波那契数列

f(0) = 0, f(1) = 1, 当n>=2时， f(n) = f(n-1) + f(n-2) 输入n,求f(n)。

朴素递推: 时间复杂度：O(n)O(n)

1
2
3
4
def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1) + fibo(n-2)

动态规划: 时间复杂度：O(n)O(n)，空间复杂度：O(n)O(n)

1
2
3
4
5
6
7
8
def fibo(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

动态规划改进：时间复杂度：O(n)O(n)，空间复杂度：O(1)O(1)

1
2
3
4
5
6
7
8
def fibo(n):
    if n <= 1:
        return n
    first_number = 0
    second_number = 1
    for _ in range(n):
        first_number, second_number = second_number, first_number+second_number
    return first_number

零钱兑换1

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

状态方程dp[i]dp[i]表示总金额为ii所对应的最少硬币个数，初始状态：dp[0]=0dp[0]=0;

状态转移方程：dp[i]=dp[i−coin]+1dp[i] = dp[i-coin]+1，不存在则为-1；

1
2
3
4
5
6
7
8
9
10
11
def coin_change(coins, amount):
    dp = [0xffffff] * (amount + 1)
    dp[0] = 0 # 初始状态，总金额为0，硬币数为0
    for i in range(amount + 1): # 外层循环是总金额
        for coin in coins:
            if i >= coin and dp[i - coin] < dp[i] - 1:
                dp[i] = dp[i - coin] + 1
    if dp[amount] != 0xffffff:
        return dp[amount]
    else:
        return -1

零钱兑换2

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

状态方程dp[i]dp[i]代表总金额为ii时所对应的硬币组合数；

状态转移方程：dp[i]=∑_j=1kdp[i−j]dp[i]=\sum\_{j=1}^{k} dp[i-j]， k为硬币面值个数；

1
2
3
4
5
6
7
8
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1 # 初始状态，总金额为零，组合数为1(所有硬币数都为0)
    for coin in coins: # 外层循环是硬币，用前面面值的硬币组成i的组合数
        for i in range(1, amount + 1):
            if i >= coin:
                dp[i] = dp[i] + dp[i - coin]
    return dp[amount]

二维矩阵求路径次数

一个(m+1)×(n+1)(m+1)\times (n+1) 的二维矩阵，从左上角走到右下角，每次只能往右走或往下走，那么到达右下角总共有多少种走法？

解1：排列组合；
假设m次往下走，n次往右走，那么走法有C_m+nmC\_{m+n}^m;

解2：动态规划；
到达一个点的路径总数=到达上面一个点的路径总和+到达左边一个点的路径总和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def path_number(m,n):
    """
    m+1行，n+1列
    """
    dp = [0] * (m+1)
    for i in range(m+1):
        dp[i] = [0] * (n+1)
    dp[0][0] = 1
    for i in range(0, m+1):
        for j in range(0, n+1):
            if i == 0 and j == 0:
                continue
            dp[i][j] = dp[i-1][j] * (i-1) >= 0 + dp[i][j-1] * (j-1) >= 0)
    return dp[m][n]

复杂版： 矩阵中存在某些点不能通过时
在状态转移的时候判断：
如果当前点不能通过，dp[i][j]=0；否则 dp[i][j]= dp[i-1][j]*(i-1)>=0+ dp[i][j-1]*(j-1)>=0)

剪绳子

给你一根长度为n的绳子，请把绳子剪成m段（m, n都是整数，n > 1 并且 m > 1），每段绳子的长度记为k[0], k[1], … , k[m]。请问它们的乘积可能的最大值是多少？例如，当绳子的长度为8时，我们把它剪成长度为2、3、3的三段，此时得到的乘积最大，是18.

解1：动态规划；时间复杂度为O(n2)O(n^{2})，空间复杂度为O(n)O(n);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def max_product( n):
    """动态规划"""
    if n < 2:
        return 0
    elif n == 2: # 注意，至少要剪成两段
        return 1
    elif n == 3:
        return 2

    products = [0] * (n + 1)
    for i in range(4):
        products[i] = i

    for i in range(4, n + 1):
        max_val = 0
        for j in range(1, i // 2 + 1):
            product = products[j] * products[i - j]
            if max_val < product:
                max_val = product
                products[i] = max_val
    #print(products)
    return products[n]

解2：贪婪算法；时间、空间复杂度为：O(n)O(n)

数学上可以证明，当n>=5时，尽可能多的剪长度为3的绳子，且最后一段绳子如果是4的话，把它剪成2+2的两段。

证明：当n >= 5时，下列不等式恒成立 3(n-3) >= 2(n-2) > n。 因此，当n大于等于5时，尽可能剪成长度为3或2的小段，并且尽可能剪成长度为3的小段。并且当n=4时，剪成2+2比1+3更好。证毕！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def max_product2(n):
    """贪婪算法"""
    if n < 2:
        return 0
    elif n == 2:
        return 1
    elif n == 3:
        return 2

    times_of_2 = 0
    times_of_3 = 0

    times_of_3 = n // 3
    if n % 3 == 1:
        times_of_3 -= 1
    times_of_2 = (n - times_of_3 * 3) / 2

    return int(3 ** times_of_3 * 2 ** times_of_2)

三角形最短路径

给定一个三角形，从上到下找到最小路径和。 您可以移动到下一行的相邻数字的每一步。
例如，给出以下三角形
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
从顶部到底部的最小路径和为11（即，2 + 3 + 5 + 1 = 11）。

解：从三角形最下面向上面推。
状态方程定义：dp[i,j] 表示从底部递推到 [i, j]位置的最小路径值。
状态转移方程：dp[i,j] = min(dp[i+1,j ], dp[i+1, j+1])+triangle[i, j]

1
2
3
4
5
6
7
8
9
def minimumTotal(triangle):
    n = len(triangle)
    if n == 1:
        return min(triangle[0])
    dp = triangle
    for i in range(n-2, -1, -1):
        for j, val in enumerate(triangle[i]):
            dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + val
    return dp[0][0]

编辑距离问题

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。可以对word1进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

解：dp[i][j]为word1前i个字符转换成word2前j个字符的最少步数。
状态转移方程存在四种情况：

edit[i][j]={0i=0,j=0ji=0,j>0ii>0,j=0min⁡(edit[i−1][j]+1,edit[i][j−1]+1,edit[i−1][j−1]+flag)i>0,j>0edit[i][j]= \begin{cases} {0} & {i=0, j=0} \\\\ {j} & {i=0, j>0} \\\\ {i} & {i>0, j=0} \\\\ {\min (edit[i-1][j]+1, edit[i][j-1]+1, edit[i-1][j-1]+flag)} & {i>0, j>0} \end{cases}

其中flag={0A[i]=B[j]1A[i]≠B[j]flag=\begin{cases}{0} & {A[i]=B[j]} \\ {1} & {A[i] \neq B[j]}\end{cases}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def min_distance(word1, word2):
    m = len(word1)
    n = len(word2)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]  # dp[i][j]表示word1前i个字符转换成word2前j个字符的最少步数
    for i in range(m + 1): dp[i][0] = i  # word1前i个字符转换为长度为0的字符，全部删除即可
    for j in range(n + 1): dp[0][j] = j  # word1是空字符，转换为长度为j的字符，逐个插入即可
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])  # delete, insert, replace
    return dp[m][n]
print(min_distance("horse", "ros")) # 3

联系作者