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

1、面试题08

题目描述：三步问题

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

示例 1: 输入：n = 3

输出：4

说明: 有四种走法 

示例 2: 输入：n = 5

输出：13

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

解题思路

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

令  表示爬  阶楼梯的总方案数，原问题被划分为了多个求最优值的子问题，继续思考，不难发现小孩爬楼梯只有三种选项，一次上 1、2、3 阶，因此  的值仅由  、 、  的值决定，因此符合「最优子结构」原则。

再进一步思考，   的取值与   、   、   的数值是如何得到的无关，因此符合「无后效性」原则。

由于小孩只有三种爬楼选项，因此  的值仅由决定。且由于爬楼的最后一步不同，因此  的值由   累加得到，即如下所示：

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

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 状态」的确定需要满足「最优子结构」与「无后效性」。

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

令  表示从左上角到坐标  的路径数字和最小值，原问题即可被划分为多个求最优值的子问题，且由于每次只能向下或向右移动一步，因此  的取值由  和  的值决定，即符合「最优子结构原则」。

进一步验证，可以发现，   的取值与   和   所对应的具体路径无关，因此符合「无后效性」。

此处啰嗦一下。如果题目改为每次可以向上、下、左、右移动一步，且不能走重复的格子，则  的值虽然与  、  、 、  的值有关，但由于「不能走重复的格子」这一限制，  所对应的具体路径会影响到  的取值，即不符合「无后效性」。

由于只能向下或向右移动一步，且由于其最后一步不同，因此  由  和 中的最小值转移得到，即如下所示：

注意，   表示坐标   处的数字大小，   ，转移时需要注意不要越界。

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. 乘积最大子数组

题目描述

示例 1:

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

示例 2:

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

解题思路

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

例如给出  ，根据上述 f[i] 的定义，我们可以得到  。不难发现  ，  的值与  的值无关，即 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]);}

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 转移方程」
  

• 分类讨论，细心枚举

推荐阅读文章

[1] 
[2] 
[3] 
[4] 
[5] 
[6] 

[7] 

[8] 

[9] 

[10] 

[11] 

[12] 

[13] 

[14] 

[15] 

[16] 

[17] 

[18] 

[19] 

[20] 

   ......

点击"在看"了解更多精彩内容

转载是一种动力 分享是一种美德

Bilibili : 洛必达数数

CSDN博客：算法之美DL

GitHub：statisticszhang