翻译自:https://blogarithms.github.io/articles/2019-03/cracking-dp-part-one

动态规划(下称 DP)是个大麻烦。 我听到不少我的同事和晚辈抱怨动态规划,它多么地不直观。 此外,大多数公司的招聘题目中经常问到 DP 问题。所以,对于一个关于算法的博客来说这是一个好的主题。

这篇文章,我会讨论下面三个问题:

  • Coin Change Problem
  • 0-1 Knapsack Problem
  • DP on grids

之后,我将留下一些经典的变种 DP 问题作为练习。

If you’re already fully confident of why/how the above DP algorithms work correctly, then reading this article may yield little value, and you may be better off waiting for the next article on DP. :)

DP 简介

我发现递归是解决 DP 问题最友好的方式。 对我来说,递归(可以让问题)非常直观。 虽然 DP 有时候看起来确实令人困惑,但从我个人经验中发现,用递归思考解决方案和问题使得 DP 问题更容易。 让我们来看一个例子。

The Coin Change Problem

你有无限数量的 K 种不同面值的硬币,你需要使用最少的硬币数量凑齐 N 美元。 例如,如果 K = 2 且面值为 {1,2},你要找到最少数量的硬币凑够 N = 9 美元。 这里非常直观的知道是 5 枚硬币(4 个 2 美元和 1 个 1 美元)。

注意,选择小于 N 的最大面值的贪心算法并不会得到正确答案。比如测试用例:K=3,面值={1,3,4},N=10. 贪心算法将得到 4 枚硬币(4+4+1+1),但正确答案应该是3枚硬币(4+3+3)

因此,很显然,我们需要检查所有可能的硬币选择。

现在,让我们递归地模拟问题。

定义一个函数 ff(N)返回凑齐 N 的最少硬币数量。 现在我们有 K 种面值。我们可以从总价值 N 中取出一枚硬币,这枚硬币可以是任意面值的,对吧? 也就是说,当 0 <= i <= length(denom) 时,N 可以表示为 ((N-denom[i]) + denom[i]) . 同时我们知道, denom[i] 就代表着一枚硬币。 因此,f(N) = f(N-denom[i]) + 1 这是(递归)的一般情况。 那什么是基准条件呢? 当 N = 0 时,我们需要 0 个硬币。 类似的,当 N < 0时,这是不可能的条件,我们也需要处理。 根据这些分析,我们可以写出:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
>> def f(n, denom):
       ans = 10**10
       if n<=0:
           return 0
       for i in denom:
           if n-i>=0:
               ans = min(ans, 1+f(n-i, denom))
       return ans
>>> f(10, [1,3,4])
3

现在,如果我们打算移植这个 DP 算法到别的场景,我们需要保证我们正在处理的一些事情: * 在函数中不应修改全局变量 * 简单,状态可记忆(state-space reduction)

接着,我们可以将denom 设置为全局数组,得到只有一个参数的函数,也就是当前总值 N。至此,我们得到一个复杂度为 O(N*K) 的 DP 解决办法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
>>> dp = [-1 for i in range(n)]
>>> def f(n):
        if dp[n]!=-1:
            return dp[n]
        ans = 10**10
        if n<=0:
            return 0
        for i in denom:
            if n-i>=0:
                ans = min(ans, 1+f(n-i))
        dp[n] = ans
        return ans

The 0-1 Knapsack Problem

现在假设你是个窃贼,你有个能装下重量为 W 的背包。

在你闯入的房子里,有 N 个贵重物品,对于物品 i 有着 wt[i] 的重量和 vals[i] 的价值。

你的任务是设计一个算法,在背包所能装下的前提下拿走总价值最大的物品。

希望你没有把这个当真 :P

让我们递归的思考问题。通常来说,每当问题有多个解决方案,其中有一种选项是可以选择或忽略某个元素时,我发现这种情况适合使用当前元素作为参数。 所以,这意味着我的函数 f()已经有了一个参数 —— int idx 现在,我们要思考剩下的参数。 在任意时刻,对于当前索引 idx 我们可以选择:拿走它,或不拿。 DP 的重点是优化我们“检查所有可能性”的解决方案,不要重复检查已检查的可能性,对吧? 所以,我们可以选择:拿走当前物品,或者不拿。 而且,当我们说拿走——我们还需要检查我们的背包是否能容纳得下。 让我们来看这个递归。为了确保我们目前得可能性是有效的,并且确保我们(的背包)是否能承受下一个目标的重量,我们需要知道当前背包剩余的容量。 所以我们的状态是(current_index, weight_left). 现在我们来看下如何进行递归建模: f(current_index, weight_left) = max( f(current_index + 1, weight_left), vals[current_index] + f(current_index+1, weight_left - wt[current_index]) ) 仔细观察该等式的右边。

f(idx, weight) = max( 我们不拿当前物品情况, 我们拿了当前物品情况)

特别值得注意的是。我们将 f(idx, weight) 定义为我们处于索引 idx 并且(背包)剩下 weight 重量时可以获得的最大价值。 两外,要注意后一种可能的状态,我们需要更新 weight_left 参数以反映我们正在挑选当前物品的事实。 (代码)看起来这样:(我不小心改变了状态的顺序,但这没关系)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def brute(weightleft, idx):
    if idx >= n:
        return 0
    if dp[weightleft][idx] != -1:
        return dp[weightleft][idx]
    ans = 10**10
    ans = brute(weightleft, idx+1)
    if wts[idx] <= weightleft:
        ans = max(ans, vals[idx] + brute(weightleft - wts[idx], idx+1))
    dp[weightleft][idx] = ans
    return ans

# call the function as brute(W, 0)

DP On Grids

这是一种非常常见的 DP 问题。 考虑下面的例子: 给定一个 N*M 的网格,每个格子都有一定数量的黄金,找到你能收集到的黄金最大数量,必须遵守一下规则:

  • 从左上角开始
  • 在右下角结束
  • 你只能移动到你右边或者下方的单元格

你需要在时间复杂度 O(N*M) 内找到解决问题的办法。 再次,我们考虑递归。 如下,我画了一个简单 3 * 3 的网格,我用 1-9 标记它们: 1 2 3 4 5 6 7 8 9 注意,这些数字只是标记网格并不是它们的价值,它只是用于唯一标识网格方便我们进行讨论。 让我们看向网格 5.由于我们只能向右或向下,唯一能到达网格 5 的办法是先走到网格 2 或者走到网格 4. 同样来说,对于网格 8. 唯一能到达 8 的办法是先到 5 或者 7. 在任何情况下,我们只能从上面网格或者左边网格访问到一个格子。 这意味着,对于任何一个节点,我们能得到的最大值为 f(node) = val[node] + max(f(upper_neighbor), f(left_neighbor)) 就是这样! 这就是我们的递归等式。我们转化为代码,我们自底而上的做到了这点:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
dp = [[0 foar i in range(m)] for j in range(n)]

dp[0][0] = A[0][0] # the top left element has a max value of itself

for i in range(n):
        for j in range(m):

                # first row
                if i==0 and j!=0:
                        dp[i][j] = dp[i][j-1] + A[i][j]
        
                # first column
                elif i!=0 and j==0:
                        dp[i][j] = dp[i-1][j] + A[i][j]
        
                # general case
                else:
                        dp[i][j] = A[i][j] + max(dp[i-1][j], dp[i][j-1])

print(dp[n-1][m-1])

这里有一道作业可供你练习。 这相当简单,我会在下一篇 DP 文章中对它进行一些解释。

给定一个 N x M 的网格,找到能走出网格的路线数量,同样遵守从左上角开始,右下角走出,并且只能往下或往右走。要求复杂度: O(N*M).

附加题:在复杂度 O(N+M) 完成。

总结

DP 有两个方面需要注意:

  • 确定你的状态
  • 确定这些状态的递归关系

希望这篇文章能够帮你更直观的理解 DP。