数据结构【2】-如何理解数据结构中的动态规划【下】？

AI研习图书馆，发现不一样的精彩世界

数据

结构

动态规划知识点详解及实践【下】

上篇文章我们讲到了动态规划的基本知识点，接下来，我们将以三道LeetCode习题为例，来强化一下确定「DP 状态」和「DP 转移方程」的 DP 问题求解思路。

一、习题实战

1、面试题08

题目描述：三步问题

有一个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果取模 1000000007。

示例 1: 输入：n = 3

输出：4

说明: 有四种走法

示例 2: 输入：n = 5

输出：13

数据范围 n 范围在 [1, 1000000] 之间

解题思路

DP 问题思路主要就是确定「DP 状态」与「DP 转移方程」，因此我们首先考虑「DP 状态」。

「DP 状态」的确定有两大原则，一是「最优子结构」，二是「无后效性」，简要概括就是将原问题划分为多个子问题，且「大规模子问题最优值」仅与「小规模子问题最优值」有关，与「小规模子问题最优值」是如何得到的无关。

此题需要求出爬 n 阶楼梯的总方案数，因此很容易想到子问题是爬 i 阶楼梯的总方案数。接下来再进一步验证该状态是否符合「最优子结构」与「无后效性」两大原则。

令

表示爬

阶楼梯的总方案数，原问题被划分为了多个求最优值的子问题，继续思考，不难发现小孩爬楼梯只有三种选项，一次上 1、2、3 阶，因此

的值仅由

、

、

的值决定，因此符合「最优子结构」原则。

再进一步思考，

的取值与

、

、

的数值是如何得到的无关，因此符合「无后效性」原则。

确定完「DP 状态」后，我们再来确定「DP 转移方程」。

由于小孩只有三种爬楼选项，因此

的值仅由

决定。且由于爬楼的最后一步不同，因此

的值由

累加得到，即如下所示：

注意，

，且转移时需要注意

、

、

不要越界。

C++ 代码实现

class Solution {public: vector<int> f; int mod = 1000000007; int waysToStep(int n) { f.resize(n+1); f[0] = 1; for(int i = 1; i <= n; i++) { f[i] = f[i-1]; if(i >= 2) f[i] = (f[i] + f[i-2]) % mod; if(i >= 3) f[i] = (f[i] + f[i-3]) % mod; } return f[n]; }};

2、64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解题思路

仍然是相同的解题思路，即依次确定「DP 状态」与「DP 转移方程」，且「DP 状态」的确定需要满足「最优子结构」与「无后效性」。

此题需要求出从左上角出发，到达坐标

的路径数字和最小值。因此不难想到，子问题就是从左上角出发，到达坐标

的路径数字和最小值。

令

表示从左上角到坐标

的路径数字和最小值，原问题即可被划分为多个求最优值的子问题，且由于每次只能向下或向右移动一步，因此

的取值由

和

的值决定，即符合「最优子结构原则」。

进一步验证，可以发现，

的取值与

和

所对应的具体路径无关，因此符合「无后效性」。

此处啰嗦一下。如果题目改为每次可以向上、下、左、右移动一步，且不能走重复的格子，则

的值虽然与

、

、

、

的值有关，但由于「不能走重复的格子」这一限制，

所对应的具体路径会影响到

的取值，即不符合「无后效性」。

确定完「DP 状态」后，继续确定「DP 转移方程」。

由于只能向下或向右移动一步，且由于其最后一步不同，因此

由

和

中的最小值转移得到，即如下所示：

注意，

表示坐标

处的数字大小，

，转移时需要注意不要越界。

C++ 代码实现

class Solution {public: int minPathSum(vector<vector<int>>& grid) { for(int i = 0; i < grid.size(); i++) for(int j = 0; j < grid[0].size(); j++) { if(i == 0 && j == 0) continue; int tp = 1e9; if(i > 0) tp = min(tp, grid[i-1][j]); if(j > 0) tp = min(tp, grid[i][j-1]); grid[i][j] += tp; } return grid[grid.size()-1][grid[0].size()-1]; }};


3、152. 乘积最大子数组

题目描述

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

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解题思路

继续采用相同的解题思路，即依次确定「DP 状态」与「DP 转移方程」，且「DP 状态」的确定需要满足「最优子结构」与「无后效性」。

此题其实是「宝石挑选」问题的进阶版，即连续区间最大乘积。因此与「宝石挑选」问题的思路一致，令 f[i] 表示以 i 为右端点的连续区间最大乘积，即可将原问题划分为多个求最优值的子问题，但这个状态定义是否符合「最优子结构」原则呢？

我们可以举一个例子来进一步思考。

例如给出

，根据上述 f[i] 的定义，我们可以得到

。不难发现

，

的值与

的值无关，即 DP 状态最优值无法由更小规模的 DP 状态最优值推出，因此不符合「最优子结构」原则。

于是问题来了，怎样的状态定义才符合「最优子结构」呢？

继续思考可以发现，上述状态定义出错的原因主要在于如果

为负数，则

只会越乘越小。因此我们需要根据

的正负值进行分类讨论：

• 

• 

「以

为右端点的连续区间最小乘积」*

由此可以发现，我们需要引入新的「DP 状态」。令

表示「以

为右端点的连续区间最大乘积」，

表示「以

为右端点的连续区间最小乘积」。

不难发现

、

的取值由

、

的值推导而来，且与其具体的区间大小无关，因此同时满足「最优子结构」与「无后效性」原则。

最后我们再通过「分类讨论」，即可确定如下「DP 转移方程」：

if(nums[i] > 0) { maxn[i] = max(nums[i], maxn[i - 1] * nums[i]); minn[i] = min(nums[i], minn[i - 1] * nums[i]);}else { maxn[i] = max(nums[i], minn[i - 1] * nums[i]); minn[i] = min(nums[i], maxn[i - 1] * nums[i]);}

总结一下，此题根据「最优子结构」原则否定了第一种状态定义。否定之后进一步观察题目性质，得到了新的「DP 状态」，并通过「分类讨论」的方式推出「DP 转移方程」，使得本题得以圆满解决。

C++ 代码实现

class Solution {public: vector<int> maxn, minn; int maxProduct(vector<int>& nums) { int n = nums.size(), ans = nums[0]; maxn.resize(n); minn.resize(n); maxn[0] = minn[0] = nums[0]; for (int i = 1; i < nums.size(); ++i) { if(nums[i] > 0) { maxn[i] = max(nums[i], maxn[i - 1] * nums[i]); minn[i] = min(nums[i], minn[i - 1] * nums[i]); } else { maxn[i] = max(nums[i], minn[i - 1] * nums[i]); minn[i] = min(nums[i], maxn[i - 1] * nums[i]); } ans = max(ans, maxn[i]); } return ans; }};

二、总结

最后我们来总结一下 DP 问题的解题思路：

• 确定「DP 状态」

• 符合「最优子结构」原则：DP 状态最优值由更小规模的 DP 状态最优值推出

• 符合「无后效性」原则：状态的得到方式，不会影响后续其它 DP 状态取值

• 确定「DP 转移方程」

• 分类讨论，细心枚举