本文将分享求解个人练习中遇到的三种动态规划问题的思路过程。

路径问题

如何找到最优子结构

本章节以自由之路为例，来讨论最优子结构。

大概描述一下题目就是，给定两个字符串 ring 和 key，循环字符串ring从 00 可以向左向右遍历，来返回拼凑 key 的最小步数。两个字符串的长度 m=len(ring)m = \text{len}(\text{ring})，m=len(key)m = \text{len}(\text{key}) 的范围为 1≤n,m≤1001\leq n, m \leq 100。

暴力求解

最开始，我考虑的方法就是简单暴力地，用BFS枚举每一条路径，比较到达终点的路径：


未经过优化的BFS代码如下，其最糟糕情况下的时间复杂度为 O(nm)O(n^m)。

def findRotateSteps(self, ring: str, key: str) -> int:
    n, m = len(ring), len(key)
    stk = [(0, 0, 0)]  # 分别对应ring的初始位置，key要查询的索引和当前已经走的步数（忽略按钮的步数）
    res = inf

    while stk:
        tmp = []
        for (start_pos, query_pos, step) in stk:
            if query_pos < m:
                query_ch = key[query_pos]
                candidate_list = idx_dict[query_ch]
                for x in candidate_list:
                    d = min(abs(x-start_pos), n-abs(x-start_pos))
                    tmp.append((x, query_pos + 1, step + d))
            else:
                # 在所有路径中找到最小值
                res = min(res, step)
        stk = tmp
    return res + m

最优结构

暴力求解方法时间复杂度过高的原因是，我们遍历了太多无效的路径。

我们仍以上图的点 8 为例，实际与其相连的路径只有 22 个，如果我们知道起点到 7 和 6 的最短距离，我们只需要比较这两个就可以了，从而获得起始点到达 8 的最短距离。

从上面的描述来看，我们找到了这种最优状态的转移方式。

我们定义：

f[i][j] 为以 j 为结尾 key 中前 i 个字符所产生的最短路。其中需要满足 ring[j] = key[i]

从而我们得到如下的转移方程

f[i+1][j]=min⁡k(f[i+1][j],f[i][k]+d(k,j))f[i+1][j] = \min_{k}(f[i+1][j], f[i][k] + d(k, j))

其中 ring[k]=key[i]\text{ring}[k]=\text{key}[i] 和 ring[j]=key[i+1]\text{ring}[j]=\text{key}[i+1]。

最后返回min⁡f[−1]+m\min f[-1] + m即可，时间复杂度是 O(mn2)O(mn^2)。

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n, m = len(ring), len(key)

        idx_dict = defaultdict(list)
        for i, ch in enumerate(ring):
            idx_dict[ch].append(i)
        f = [[inf] * n for _ in range(m)]
        # 初始化
        for j in idx_dict[key[0]]:
            f[0][j] = min(j, n-j)

        for i in range(1, m):
            ch = key[i]
            for j in idx_dict[ch]:
                for pre in idx_dict[key[i-1]]:
                    diff = abs(j-pre)
                    d = min(diff, n - diff)
                    f[i][j] = min(f[i][j], f[i-1][pre]+d)

        return min(f[-1]) + m

补充

如果我们在上述动态规划中仅仅定义，f[i]f[i] 为达成 key 中前 ii 最短的步数，我们是无法找到动态转移方程的。因为下一步中的的路径计算依赖于上一步的起点信息，所以起点也是需要加入状态的。

子序列问题

如何找打最优子结构

本节以最长回文串为例讨论子序列问题的最优子结构。

大概的要求就是从一个字符串 s 中找到最长的回文串子序列。

状态定义

我最开始想到的定义是，f[i][j] 表示以 ii 开头以 j 坐标结尾的最长回文串长度，这样 f[i-1][j+1] 就可以靠比较 f[i][j] 和 s[i]==s[j]s[i] == s[j] 来完成。但是这样的定义有一个问题就是，要求过于严格，成为了一个连续的子串而不是子序列。

假如 f[i−1][j−1]=0f[i-1][j-1]=0 而 s[i]==s[j]s[i]==s[j]，那么这个子序列的长度一定为 22 嘛？根据子序列的要求，我们还可以比较 f[i−2][j−1]f[i-2][j-1] 等等组合。

因此，我们定义 f[i][j] 为 i∼ji \sim j 这个闭区间的最长回文子序列长度。得到的状态转移方程为:

f[i−1][j+1]={f[i][j]+2if s[i]==s[j]max⁡(f[i−1][j],f[i][j−1])if s[i]!=s[j]f[i-1][j+1] = \left \{ \begin{matrix}f[i][j] + 2 & if \, s[i]==s[j]\\ \max(f[i-1][j],f[i][j-1]) & if \, s[i]!=s[j] \end{matrix}\right.

不相等的时候，分别取两个左右区间的最大值。

根据题意，ii 是递减的，jj 是递增的。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        f = [[0]*n for _ in range(n)]

        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if i == j:
                    f[i][j] = 1
                    continue
                if s[i] == s[j]:
                    f[i][j] = f[i+1][j-1] + 2  # f[i+1][j-1] = 0
                else:
                    f[i][j] = max(f[i][j-1], f[i+1][j])
                # if j == i + 1:
                #     f[i][j] = 2 if s[i] == s[j] else 1
                #     continue
                # if s[i]!=s[j]:
                #     f[i][j] = max(f[i][j-1], f[i+1][j])
                # else: 
                #     f[i][j] = f[i+1][j-1] + 2
        # print(f)
        return f[0][n-1]

背包问题

如何找到最优子结构

本节将以一个零钱兑换讲解状态DP的求解思路（背包问题我也喜欢叫做状态DP的一种特例）。

题目大意是给定无线数量的各种面值的硬币 coins 问可以拼凑出 amount 数值的组合数。

状态定义

很显然我们可以定义状态 f[i][j] 为前 ii 个硬币中达成面值为 jj 的组合数量。得到状态转移方程为

f[i+1][j]=f[i][j]+f[i+1][j−x]f[i+1][j] = f[i][j] + f[i+1][j-x]

其中 xx 为当前硬币的面额。

为什么我们只考虑 f[i+1][j-x] 这种一次的情况呢。因为根据递推，所有到达 jj 的情况都要经过 j−xj-x，所以已经是汇总无重复的情况了。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # coins.sort()
        
        # tmp = []
        # for i, val in enumerate(coins):
        #     div = amount // val
        #     if div:
        #         tmp.append(val)

        # if not coins:
        #     return 0
        
        ans = 0
        # coins = tmp
        n = len(coins)
        # O(mn) ~ 10^6
        f = [[0] * (amount+1) for _ in range(n+1)]
        f[0][0] = 1
 
        for i in range(1, n+1):
            x = coins[i-1]
            for j in range(amount+1):
                if j < x:
                    f[i][j] = f[i-1][j]
                else:
                    f[i][j] = f[i-1][j] + f[i][j-x]
        return f[-1][amount]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # coins.sort()
        # insert_idx = bisect_right(coins, amount)
        # coins = coins[:insert_idx]
        n = len(coins)

        f = [0] * (amount + 1)
        f[0] = 1

        for i in range(1,n+1):
            x = coins[i-1]
            for j in range(x, amount+1):
                f[j] += f[j-x]
        
        return f[-1]

例题

现在想必你已经完全掌握背包问题了，快去刷题练习吧！