Map of Augustus's Soul

DP IS EASY —— 如何切入动态规划问题

Posted on In Valine:
Symbols count in article: 3.1k Reading time ≈ 8 mins.

是对DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions的翻译记录，原题是 Target Sum（目标和）

DP很容易！5步思考DP问题

注意：这不是一个规范化、完美优化的DP解决方案。我们已经有足够多这样的东西了。这篇文章将带领你了解动态规划背后的思考过程，让你能够自己解决这些问题。

类别

大多数动态规划问题可以归结为几个类别。识别类别很重要，因为它允许我们将一个新问题转化成我们已知的问题。转化意味着使用框架，而不是将另一个问题的解决方法复制到当前问题中。你必须明白每个DP问题都是不同的。

问题：在继续之前将此问题标识为以下类别之一。

  • 0/1背包
  • 无界背包
  • 最短路径（例如：独特的路径I/II）
  • 斐波那契数列（例如：房子小偷，跳跃游戏）
  • 最长公共子串/子序列

答案：0/1背包

为什么是0/1背包？我们的“容量”是我们想达到的目标“S”。我们的“物品”是输入子集中的数字，物品的“重量”是数字本身的值。这个问题遵循0/1背包而不是无界背包，因为我们只能使用每个数字一次。

变化是什么？这个问题与标准背包问题的变化在于，我们必须将子集中的所有物品添加到我们的背包中。我们可以将问题重新构成为将当前数字的正值或负值添加到我们的背包中，以达到目标容量“S”。

状态

我们需要跟踪哪些变量才能达到最佳结果？这篇Quora文章很好地解释了状态，请参考这个链接（如果你感到困惑）：**www.quora.com/What-does-a-state-represent-in-terms-of-Dynamic-Programming**

问题：确定状态变量。

提示：作为一般规则，背包问题至少需要2个状态。

答案：索引与当前总和

为什么是索引？

索引代表我们正在考虑的输入子集的索引。这告诉我们哪些值我们已经考虑过，哪些值我们还没有考虑过，以及我们当前正在考虑的值。一般规则是，在几乎所有的动态规划问题中都需要索引状态，除了最短路径，它的状态是行和列而不是单个索引，但我们会在另一篇文章中介绍这个问题。

为什么是当前总和？

这个问题是问我们是否可以对子集中的每个数（该数的正值或负值）求和以达到目标值。 Current Sum 为我们提供了迄今为止我们已处理的所有值的总和。 我们的答案围绕着 Current Sum 等于 Target。

决策

动态规划就是做出最佳决策。 为了做出最佳决策，我们必须首先尝试所有决策。 MIT 关于动态规划的课程讲义（The MIT lecture on DP）（强烈推荐）将此称为猜测步骤。 我的大脑更擅长将此称为决策而不是猜测。 决策必须使我们更接近基本情况（Base Case），并引导我们找到我们想要回答的问题。 基本情况在第 4 步中涵盖，但实际上与决策步骤协同工作。

问题：在每次递归调用时我们必须做出什么决定？ 提示：一般来说，背包问题需要 2 个决定。

答案：这个问题要求我们在输入子集中获取所有数，因此在每一步中我们都会向背包中添加一个数。 请记住，我们在第 2 步中声明“该问题询问我们是否可以对子集中的每个数（该数的正值或负值）求和以达到目标值。” 决策包括：

  • 我们应该添加当前数字的正值吗
  • 我们应该添加当前数字负值吗

请注意，背包问题通常不需要我们拿走所有物品，因此通常的背包决定是拿走物品或留下物品

基本情况（Base Case）

基本情况需要与我们正在寻求的答案所需的条件直接相关。 这就是为什么我们的决策朝着我们的基本情况努力很重要，因为这意味着我们的决策正在朝着我们的答案努力。

让我们重新审视我们的答案的条件：

  • 我们使用输入子集中的所有数字。
  • 所有数字的总和等于我们的目标“S”。

问题：确定基本案例。 提示：有 2 个基本案例。

答案：我们需要 2 个基本案例。 一种用于当前状态有效时，一种用于当前状态无效时。

  • 有效：索引超出范围且当前总和等于目标“S”
  • 无效：索引越界

为什么索引越界？

我们答案的一个条件是我们使用输入子集中的每个项目。 当索引超出范围时，我们知道我们已经考虑了输入子集中的每个项目。

为什么当前总和等于目标？

我们的答案的一个条件是在我们的输入子集中使用的数的正值或负值的总和等于目标总和“S”。

如果我们已经考虑了输入子集中的所有数并且我们当前的总和等于我们的目标，那么我们已经成功地满足了我们答案要求的两个条件。

另一方面，如果我们已经考虑了输入子集中的所有数，并且我们当前的总和不等于我们的目标，那么我们只满足了答案所要求的条件之一。说明无最终答案。

写代码吧

如果您已经考虑了所有步骤并理解了问题，那么编写实际解决方案的代码就很简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def findTargetSumWays(self, nums, S):
     index = len(nums) - 1
     curr_sum = 0
     return self.dp(nums, S, index, curr_sum)
     
 def dp(self, nums, target, index, curr_sum):
 	# Base Cases
     if index < 0 and curr_sum == target:
         return 1
     if index < 0:
         return 0 
     
 	# Decisions 决策
     positive = self.dp(nums, target, index-1, curr_sum + nums[index])
     negative = self.dp(nums, target, index-1, curr_sum + -nums[index])
    
    return positive + negative

优化

一旦我们引入记忆化（memoization），我们将只解决每个子问题一次。 我们可以完全删除递归，并通过引入制表来避免开销和堆栈溢出的可能性。 重要的是要注意自上而下的递归和自下而上的制表方法执行完全相同的工作量。 唯一不同的是内存。 如果他们执行完全相同的工作量，转换只需要我们指定解决问题的顺序。 这篇文章现在真的很长，所以我不会在这里介绍这些步骤，可能会在以后的文章中介绍。

使用记忆化的方案供参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findTargetSumWays(self, nums, S):
        index = len(nums) - 1
        curr_sum = 0
        self.memo = {}
        return self.dp(nums, S, index, curr_sum)
        
    def dp(self, nums, target, index, curr_sum):
        if (index, curr_sum) in self.memo:
            return self.memo[(index, curr_sum)]
        
        if index < 0 and curr_sum == target:
            return 1
        if index < 0:
            return 0 
        
        positive = self.dp(nums, target, index-1, curr_sum + nums[index])
        negative = self.dp(nums, target, index-1, curr_sum + -nums[index])
        
        self.memo[(index, curr_sum)] = positive + negative
        return self.memo[(index, curr_sum)]

对您希望此类帖子在下一篇文章中遇到的 DP 问题发表评论，如果您觉得有帮助，请为该解决方案点赞。 我想把它推到首位，因为我真的厌倦了看到直接优化的表格解决方案，背后没有任何思考过程。

DP IS EASY!

谢谢。