动态规划的解题思想

2024年 第18篇

• 从斐波那契数列说起

• 何为动态规划

• 何时&如何使用动态规划

• 经典题目

• 空间复杂度的优化

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始， ，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(2) = 1

F（n） = F（n - 1） + F（n - 2），其中 n >= 2

给定 n ，请计算 F(n) 。

当我们看完上述问题后，心中一阵窃喜：答案不就在题目当中吗。

于是马上就写出了如下代码：

#暴力递归
def fib(n):
    if n == 0or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)

不幸的是，当我们提交完代码后，大概率会收到 leetcode 的超时警告！why，接下来我们分析一下上述代码的执行情况。假设 n=5 时，具体的执行逻辑如下图所示：

我们不难发现 fib(3) 计算了两次。如果这个差距不够明显的话，我们可以假设 n=10，再去画执行逻辑图，就会发现需要重复计算的情况成指数级增长，这就是耗时的主要原因。

然后我们想出了一种空间换时间的方法，把每次 fib 函数计算的结果缓存到一个哈希表中，下次再遇到相同的数则无需计算，直接查表即可，这样就大大减少了运算量。

#备忘录递归
map = {}
def fib(n):
    if n == 0or n == 1:
        return n
    elif n in map:
        return map[n]
    map[n] = fib(n - 1) + fib(n - 2)
    return map[n]

上述解法通常被命名为备忘录递归解法，事实上备忘录递归法和动态规划只是在实现上稍有不同，其核心思想和目标完全一致，拆分子问题，记住过往，减少重复计算，甚至个人认为备忘录递归就是广义上的动态规划。

动态规划就是将一个问题拆分为若干的子问题，直到子问题被解决，保存子问题结果，然后递推出原问题的答案。

同样是上面的例子，我们既然知道 1 和 2 的值，就能推算出 3，4....n 的值。

我们不妨来定义一个数组 nums，nums[i] 表示斐波那契的第 i 项，递推的给数组赋值，返回第 n 项即为所求结果。不过为了强调动态规划，我们通常会将这个数组命名为 dp（Dynamic Programming）。

#动态规划解法
def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

通过上述的例子，相信大家已经对动态规划有了一些认识，那么什么情况下我们可以使用动态规划呢？

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

如何使用动态规划的思想解题呢？

1. 找到相同问题（也叫重叠子问题），这个相同问题必须能适配不同规模

2. 找到相同问题 不同规模之间的关系（这个关系叫状态转移方程）

3. 找到问题的特殊解，然后递推出所有规模的解

（简单的理解就是：定义 dp 表格的含义，找出后边数据和前边数据的关系，然后依次填表，直到找出最终解）

本节比较抽象，大家可以看完下一节的经典题目后再回来理解。

还是回到上面的例子，我们之所以能很容易写出上面代码，是因为题目中已经把状态转移方程直接写到了题目中。而大部分情况这个方程并非那么明显，需要我们去分析，这也是动态规划的难点所在。

「 4.1 打家劫舍 」

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1，2，3，1]

输出：4

解释：偷窃 1 号房屋 （金额 = 1） ，然后偷窃 3 号房屋 （金额 = 3）。     偷窃到的最高金额 = 1 + 3 = 4 。

第一步找到重叠子问题，要适配所有的规模。因为这是一个一位数组所有使用 dp[i] 就能表示所有的规模，那么 dp[i]表示什么含义呢？表示小偷从 0-i 范围内可以偷窃的最高金额。

第二步列状态转移方程。分析下图前 i 项的最大值，包含两个情况，要么包含第 i 项要么不包含第 i 项。

如果不包含第 i 项， 则 dp[i] = dp[i-1]

如果包含第 i 项，由于相邻的房屋不能偷窃，则一定不能包含第 i-1 项，所以 dp[i] = dp[i-2] + 数组的第 i 项的值

由于求的是最优的结果  所以 dp[i] 应该是以上两种情况中值较大的情况。

列出方程 dp[i] = max(dp[i-1], dp[i-2]+nums[i])

第三步确定特殊解，当房屋数等于 1 时，最优解就是只偷一间；当房屋数等于 2 时，最优解就是偷价值较大的一间。

接下来递推填表，返回最终解。

「 4.2 不同路径 」

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

首先第一步，我们要找到重叠子问题，这些子问题要能适配所有的规模。这里有行也有列，所以我们需要两个参数来表示这个子问题  dp[i][j]，表示的含义就是从开始走到第 i 行第 j 列的所有路径数。

第二步，确定状态转移方程。观察下图，我们会发现 dp[i][j]的路径数只和两个格子有关 dp[i][j-1]和 dp[i-1][j]，且是他们两个的和，所以状态转移方程应该是 dp[i][j] = dp[i][j-1] + dp[i-1][j]

第三步，确定特殊解，第 1 行和第 1 列所有的数据都只有一种情况，要么一直向右走要么一直向下走，所以全部赋值为 1，然后递推填表，直到返回最终结果。

「 4.3 01 背包 」

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

示例 1：

物品重量为：[1，3，4]

物品价值为：[15，20，30]

背包能背的最大重量为：4

输出最大价值：35

解释：背包可以放入 0 和 1 号商品，价值为 15+20=35，也可以只放 2 号商品，价值为 30。

第一步找重叠子问题，确定 dp 表含义。

按照前面的经验我们通常会将 dp[i]定义为 从 0 到 i 最优的情况，干脆我们也将 dp[i] 定义为 从 0 到 i 件商品中可选的最大价值。然而我们继续往下分析时，并没有找到不同规模问题之间的联系。

另一方面我们还可以从背包容量上拆分子问题，比如如果知道背包容量为 3 时的最大价值，是否可以推导出容量为 4 时的最大价值，经过一番思考计算，好像也找不到不同规模之间的联系。

此时聪明的你，一定能想到，要不然将以上两个纬度同时进行拆分找一下其中的规律。那么我们就会得到下面一个二维 dp 表。其中 dp[i][j] 表示从 0-i 中选择的物品放入容量为 j 的背包中的最大价值

第二步分析不同规模问题之间的联系，列出状态转移方程

此时有两种情况，i 物品选还是不选。此时状态表达式有了一个基本的雏形：

dp[i][j] = max（选第 i 件商品，不选第 i 件商品）。

首先看不选的情况，这种情况比较简单，如果不选那么最大价值就等于同等容积背包内，前面商品所能凑出的最大价值。直接写出表达式 dp[i][j] = dp[i-1][j]

接下来分析选的情况，如果选择了第 i 个商品 那么此时的最大价值应该是 商品i本身的价值 + 商品i-1范围内 且 背包容量为(j-商品i的重量)的最大价值，写成表达式为dp[i][j] = value[i] + dp[i-1][j-weight[i]]

综上最终的表达式为  dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])，另外还需要处理一些边界条件，例如当商品本身重量大于背包容量时等。此处就不展开描述了。

第三步找出特殊解

当物品下表为 0 时，之前看当前商品是否可以放入背包内，可以放入最大价值就是当前商品价值，否则最大价值就是 0，然后递推填表。

学到这里，恭喜你，你已经拿到了 leetcode 刷动态规划类题目的入场券！

最后我们再来聊一下空间复杂度的优化。

上面我们说过，动态规划的核心就是记住过往，减少重复计算， 牺牲空间去换取时间，那么我们到底牺牲了多少空间？

回到斐波那契数列，我们定义了一个长度为 n 的数组来缓存过程中的计算结果，所以空间复杂度为 O(n)，然后仔细观察我们就会发现，当我们计算 dp[i] 时，并不需要整个数组，而是只需两个数字。所以我们只需定义两个数据，每次记得更新数据即可。这样就可以将空间复杂度降低到常量级 O(1)。

接下来我们看不同路径的题目，在这里我们定义了一个二位数组，所以空间复杂度为 O(m*n)；继续观察我们发现 dp[i][j] 只和当前行和上一行的数据关联。那我们就可以这样做，定义一个一维数组，先把数组全部填充 1（相当于二维数组的第一行），之后的行从左往右覆盖当前的一维数组，假设覆盖到了第 i-1 位，此时一位数组的含义，i 左边的数据表示的是当前行的数据，i 及右边的数据表示上一行的数据。原本的状态转移方程dp[i][j] = dp[i][j-1] + dp[i-1][j]就可以优化成 dp[i] = dp[i-1]+dp[i]，空间复杂度也降到了 O(n)

这里总结出来，很多动态规划问题可以通过“空间降维”只缓存当前被需要的数据，来降低空间复杂度。

「三翼鸟数字化技术平台-场景设计交互平台」主要负责设计工具的研发，包括营销设计工具、家电VR设计和展示、水电暖通前置设计能力，研发并沉淀素材库，构建家居家装素材库，集成户型库、全品类产品库、设计方案库、生产工艺模型，打造基于户型和风格的AI设计能力，快速生成算量和报价；同时研发了门店设计师中心和项目中心，包括设计师管理能力和项目经理管理能力。实现了场景全生命周期管理，同时为水，空气，厨房等产业提供商机管理工具，从而实现了以场景贯穿的B端C端全流程系统。

_________________ END__________________