什么样的问题应使用动态规划求解

前言一、求“最”优解问题（最大值和最小值）1. 乘积最大子数组问题描述示例题目分析参考代码 2. 最长回文子串问题描述示例题目分析参考代码 3. 最长上升子序列问题描述示例题目分析参考代码 二、求可行性（True 或 False）1. 凑零兑换问题问题描述示例题目分析参考代码 2. 字符串交错组成问题问题描述示例题目分析参考代码 三、求方案总数1. 硬币组合问题问题描述示例题目分析参考代码 2. 路径规划问题问题描述示例题目分析参考代码 四、数据不可排序1. 最小的 k 个数问题描述示例题目分析 五、数据不可交换（Non-swapable）1. 全排列问题描述示例题目分析 总结与升华个人介绍

前言

算法是一种经验总结，而思想则是用来指导我们解决问题的。

动态规划是一个指导我们解决问题的思想：

你需要利用已经计算好的结果来推导你的计算，即大规模问题的结果是由小规模问题的结果运算得来的。

事实上，动态规划是运筹学上的一种最优化方法，只不过在算法问题上应用广泛。接下来我们就深挖一层，看看动态规划问题所具备的一些特点。

一、求“最”优解问题（最大值和最小值）

既然是要求最值，不妨先想一下核心问题是什么。其实在真的解决最值问题的时候，你应该按照这样的思考顺序来解决问题：

优先考虑使用贪心算法的可能性；然后是暴力递归进行穷举（但这里的数据规模不大）；还是不行呢？选择动态规划！

你也看到了，求解动态规划的核心问题其实就是穷举。那么因为我们要求最值，就肯定要把所有可行的答案穷举出来，然后在其中找最值就好了嘛。

当然了，动态规划问题也不会这么简单了事，我们还需要考虑待解决的问题是否存在重叠子问题、最优子结构等特性。

1. 乘积最大子数组

问题描述

给你一个整数数组 numbers，找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），返回该子数组的乘积。

示例

示例1： 输入: [2,7,-2,4] 输出: 14 解释: 子数组 [2,7] 有最大乘积 14。 示例2： 输入: [-5,0,3,-1] 输出: 3 解释: 结果不能为 15, 因为 [-5,3,-1] 不是子数组，是子序列。

题目分析

首先，很明显这个题目当中包含一个“最”字，使用动态规划求解的概率就很大。

这个问题的目的就是从数组中寻找一个最大的连续区间，确保这个区间的乘积最大。由于每个连续区间可以划分成两个更小的连续区间，而且大的连续区间的结果是两个小连续区间的乘积，因此这个问题还是求解满足条件的最大值，同样可以进行问题分解，而且属于求最值问题。

同时，这个问题与求最大连续子序列和比较相似，唯一的区别就是你需要在这个问题里考虑正负号的问题，其它就相同了。

参考代码

def maxProduct(nums): if len(nums) == 0: return 0 length = len(nums) # 初始化 # dp 数组有两个元素，一个存储最大值，一个最小值 dp = [[0] * 2 for _ in range(length)] # 初始化数组首元素为最大值和最小值 dp[0][0] = nums[0] dp[0][1] = nums[0] #　开始遍历 for i in range(1, length): # 状态转移方程 if nums[i] > 0: dp[i][0] = min(nums[i], dp[i-1][0] * nums[i]) dp[i][1] = max(nums[i], dp[i-1][1] * nums[i]) else: dp[i][0] = min(nums[i], dp[i-1][1] * nums[i]) dp[i][1] = max(nums[i], dp[i-1][0] * nums[i]) # 因为最终要求得最大值，那么在 dp[i][1] 找得最大即可 # 初始化返回值 res = dp[0][1] for i in range(1, length): res = max(res, dp[i][1]) return res def main(): result = maxProduct([2,7,-2,4]) print(result) if __name__ == "__main__": main()

2. 最长回文子串

问题描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

示例1： 输入: "babad" 输出: "bab" 示例2： 输入: "cbbd" 输出: "bb"

题目分析

这个问题依然包含一个“最”字，同样由于求解的最长回文子串肯定包含一个更短的回文子串，因此我们依然可以使用动态规划来求解这个问题。

参考代码

def longestPalindrome(s): dp = [[False]*len(s) for _ in range(len(s))] max_start, max_len = 0, 0 # 最长回文子串开始位置及长度 for right in range(len(s)): # 右指针先走 for left in range(right+1): # 左指针跟着右指针 if right - left < 2: # 前两种情况 dp[left][right] = (s[left] == s[right]) else: # 最后一种情况 dp[left][right] = (s[left] == s[right]) and dp[left+1][right-1] # cur_substr = s[left:right+1] # 当前考察的子串 cur_len = right + 1 - left # 当前子串长度为 right + 1 - left if dp[left][right] and max_len < cur_len: max_start = left max_len = cur_len return s[max_start:max_start + max_len] def main(): result = longestPalindrome('abswensne') print(result) if __name__ == "__main__": main()

3. 最长上升子序列

问题描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

示例

示例： 输入: [10,9,2,5,3,7,66,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,66]，它的长度是 4。

题目分析

这个问题依然是一个最优解问题，假设我们要求一个长度为 5 的字符串中的上升自序列，我们只需要知道长度为 4 的字符串最长上升子序列是多长，就可以根据剩下的数字确定最后的结果。

参考代码

def lengthOfLIS(nums) : if not nums: return 0 dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) def main(): result = lengthOfLIS([10,9,2,5,3,7,66,18]) print(result) if __name__ == "__main__": main()

二、求可行性（True 或 False）

如果有这样一个问题，让你判断是否存在一条总和为 x 的路径（如果找到了，就是 True；如果找不到，自然就是 False），或者让你判断能否找到一条符合某种条件的路径，那么这类问题都可以归纳为求可行性问题，并且可以使用动态规划来解。

1. 凑零兑换问题

问题描述

给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

示例

示例1： 输入: c1=1, c2=2, c3=5, c4=7, amount = 15 输出: 3 解释: 11 = 7 + 7 + 1。 示例2： 输入: c1=3, amount =7 输出: -1 解释: 3怎么也凑不到7这个值。

题目分析

这个问题显而易见，如果不可能凑出我们需要的金额（即 amount），最后算法需要返回 -1，否则输出可能的硬币数量。这是一个典型的求可行性的动态规划问题。

参考代码

def getMinCounts(k, values): memo = [-1] * (k + 1) memo[0] = 0 # 初始化状态 for item in range(1, k + 1): memo[item] = k + 1 for item in range(1, k + 1): for coin in values: if (item - coin < 0): continue memo[item] = min(memo[item], memo[item - coin] + 1) # 作出决策 return memo[k] def getMinCountsDPSol(): values = [3, 5] # 硬币面值 total = 22 # 总值 # 求得最小的硬币数量 return getMinCounts(total, values) # 输出答案 def main(): result = getMinCountsDPSol() print(result) if __name__ == "__main__": main()

2. 字符串交错组成问题

问题描述

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例

示例1： 输入: s1="aabcc",s2 ="dbbca",s3="aadbbcbcac" 输出: true 解释: 可以交错组成。 示例2： 输入: s1="aabcc",s2="dbbca",s3="aadbbbaccc" 输出: false 解释:无法交错组成。

题目分析

这个问题稍微有点复杂，但是我们依然可以通过子问题的视角，首先求解 s1 中某个长度的子字符串是否由 s2 和 s3 的子字符串交错组成，直到求解整个 s1 的长度为止，也可以看成一个包含子问题的最值问题。

参考代码

def isInterleave(s1, s2, s3): # 先处理特殊情况，如果 s1 和 s2 的长度和不等于 s3 的长度，则返回 False。因为无法交错拼接 if len(s1) + len(s2) != len(s3): return False m = len(s1) n = len(s2) # 状态定义 dp = [[False] * (n+1) for _ in range(m+1)] # 初始化 dp[0][0] = True for i in range(1, m+1): dp[i][0] = dp[i-1][0] and s3[i-1] == s1[i-1] for j in range(1, n+1): dp[0][j] = dp[0][j-1] and s3[j-1] == s2[j-1] for i in range(1, m+1): for j in range(1, n+1): dp[i][j] = (dp[i-1][j] and s3[i+j-1]==s1[i-1]) or (dp[i][j-1] and s3[i+j-1]==s2[j-1]) return dp[-1][-1] def main(): result = isInterleave(s1="aabcc",s2 ="dbbca",s3="aadbbcbcac") print(result) if __name__ == "__main__": main()

三、求方案总数

除了求最值与可行性之外，求方案总数也是比较常见的一类动态规划问题。

比如说给定一个数据结构和限定条件，让你计算出一个方案的所有可能的路径，那么这种问题就属于求方案总数的问题。

1. 硬币组合问题

问题描述

英国的英镑硬币有 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), 和 £2 (200p)。比如我们可以用以下方式来组成 2 英镑：1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p。问题是一共有多少种方式可以组成 n 英镑? 注意不能有重复，比如 1 英镑 +2 个 50P 和 50P+50P+1 英镑是一样的。

示例

示例1： 输入: 200 输出: 73682

题目分析

这个问题本质还是求满足条件的组合，只不过这里不需要求出具体的值或者说组合，只需要计算出组合的数量即可。

参考代码

def coinCombination(n): array = [1] + [0] * n fan = [1,2,5,10,20,50,100,200] for i in fan: for j in range(i, n + 1): array[j] += array[j-i] return array[n] def main(): result = coinCombination(200) print(result) if __name__ == "__main__": main()

2. 路径规划问题

问题描述

一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，共有多少路径？

示例

示例1： 输入: 2 2 输出: 2 示例2： 输入: 3 3 输出: 6

题目分析

这个问题还是一个求满足条件的组合数量的问题，只不过这里的组合变成了路径的组合。我们可以先求出长宽更小的网格中的所有路径，然后再在一个更大的网格内求解更多的组合。这和硬币组合的问题相比没有什么本质区别。

这里有一个规律或者说现象需要强调，那就是求方案总数的动态规划问题一般都指的是求“一个”方案的所有具体形式。

如果是求“所有”方案的具体形式，那这种肯定不是动态规划问题，而是使用传统递归来遍历出所有方案的具体形式。为什么这么说呢？因为你需要把所有情况枚举出来，大多情况下根本就没有重叠子问题给你优化。即便有，你也只能使用备忘录对遍历进行一个简单加速。

参考代码

def uniquePaths(m, n): result = [[1] * m for _ in range(n)] for index1 in range(1,n): for index2 in range(1,m): result[index1][index2] = result[index1 - 1][index2] + result[index1][index2 - 1] output = result[-1][-1] return output def main(): result = uniquePaths(3, 3) print(result) if __name__ == "__main__": main()

四、数据不可排序

假设我们有一个无序数列，希望求出这个数列中最大的两个数字之和。

很多初学者刚刚学完动态规划会走火入魔到看到最优化问题就想用动态规划来求解。

不，等等，这个问题不是简单做一个排序或者做一个遍历就可以求解出来了吗？

所以学完动态规划后，你一定要注意，遇到这些简单的问题不要把事情变得更复杂了。先考虑一下能不能通过排序来简化问题，如果不能，才极有可能是动态规划问题。

1. 最小的 k 个数

问题描述

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。

示例

示例1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例2： 输入：arr = [0,1,2,1], k = 1 输出：[0]

题目分析

我们发现虽然这个问题也是求“最”值，但其实只要通过排序就能解决，所以我们应该用排序、堆等算法或者数据结构来解决，而不应该用动态规划。

五、数据不可交换（Non-swapable）

还有一类问题，可以归类到我们总结的几类问题里去，但是不存在动态规划要求的重叠子问题（比如经典的八皇后问题），那么这类问题就无法通过动态规划求解。这种情况需要避免被套进去。

1. 全排列

问题描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例

示例： 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

题目分析

这个问题虽然是求组合，但没有重叠子问题，更不存在最优化的要求，因此可以使用回溯处理，并不是动态规划的用武之地。

总结与升华

辨别一个算法问题是否该使用动态规划来解的五大特点：

求最优解问题（最大值和最小值）；求可行性（True 或 False）；求方案总数；数据不可排序（Unsortable）；算法不可使用交换（Non-swappable）。

如果面试题目出现这些特征，那么在 90% 的情况下你都能断言它就是一个动态规划问题。

当然了，还需要考虑这个问题是否包含重叠子问题与最优子结构，在这个基础之上你就可以 99% 断言它是否为动态规划问题。

个人介绍

北京联合大学 机器人学院 自动化专业 2018级 本科生 郑博培百度飞桨开发者技术专家 PPDE深圳柴火创客空间 认证会员百度大脑 智能对话训练师阿里云 DevOps助理工程师