算法学习笔记（8.2）-动态规划入门进阶

问题判断:

问题求解步骤：

图例：

解析：

方法一：暴力搜索

实现代码如下所示：

解析：

方法二：记忆化搜索

代码示例：

解析：

方法三：动态规划

空间优化

代码如下

问题判断:

总的来说，如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。然而，我们很难从问题的描述中直接提取出这些特征，因此通常需要放宽条件，首先需要观察问题适不适合使用回溯（穷举）解决。

适合用回溯解决的问题通常满足“决策树模型”，对于问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。

换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯解决。

在此基础上，动态规划问题还有一些判断的“加分项”。

1. 问题包含最大（小）或最多（少）等优化描述。

2. 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。

相应地，也存在一些“减分项”。

1. 问题的目标是找出所有的解决方案，而不是找出最优解。

2. 问题描述中有明显的排列组合特征，需要返回具体的对个方案。

如果一个问题满足决策树模型，并具有较为明显的“加分项”，我们就可以假设它是一个动态规划问题，并在求解过程中验证它。

问题求解步骤：

动态规划的问题解题流程会因为问题的性质和难度有所不同，但通常遵循一下步骤：描述决策，定义状态，建立dp表，推导状态转移方程，确定边界问题等。

为了理解动态规划的解题的过程，使用一个经典的例题“最短路径和”

Question：

给定一个n * m的二维网格grid，网格中的每个单元包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回左上角到右下角的最小路径和。

图例：

给定网格的最小路径和为13

第一步：思考每轮的决策，定义状态，从而得到dp表

本题的每一轮的决策就是从当前格子向下或者向右走一步。设当前格的行列索引为[i,j]，则向下或向右走一步后，索引变为[i+1,j]或[i,j+1]。因此，状态应包含行索引和列索引两个变量，记为[i,j]。

状态[i,j]对应的子问题为：从起始点[0,0]走到[i,j]的最小路径和，记作dp[i,j]。

如图所示：dp二维矩阵，其尺寸与输入网格grid相同。

注意点：（Note）

动态规划和回溯过程可以描述成为一个决策序列，而状态由所有决策变量构成。应当包含描述解题进度的所有变量，其包含了足够的信息，能用来推导下一个状态。

每个状态都对应一个子问题，我们会定义成为一个dp表来存储所有子问题的解，状态的每个独立变量都是dp表中的一个维度。从本质上看，dp表是状态和子问题的解之间的映射。

第二步：找出最优子结构，进而推导出状态转移方程

对应状态[i,j]，它只能从上边的格子[i-1，j]和左边的格子[I,j-1]转移过来。因此最优子结构为：到达[i,j]的最小路径和由[i-1，j]的最小路径和与[I,j-1的最小路径和哪个较小来决定。

根据以上的分析得出状态转移方程为：

dp[i,j] = min(dp[i-1,j],dp[i,j-1]) +grid[i,j]

图示如下：

注意点：（Note）

根据定义好的dp表，思考原问题和子问题的关系，找出通过子问题的最优解来构造原问题的最优解的方法，即最优子结构。

一旦我们找到了最优子结构，就可以使用它来构建出来状态转移方程。

第三步：确定边界条件和状态转移顺序

在本题中，处在首行的状态只能从其左边的状态得来，处在首列的状态只能从其上边的状态得来，因此首行i = 0 和首列的 j = 0 是边界条件。

如图所示，由于每个格子是由其左方格子和上方格子转移而来，因此我们使用循环来遍历矩阵，外循环遍历各行，内循环遍历各列。

解析：

根据对上面的理解我们已经可以写出动态规划的代码。然而子问题的解决是一种从顶至底的思想，因此按照“暴力搜索”->“记忆化搜索”->“动态规划”的顺序实现符合思维习惯。

方法一：暴力搜索

从状态[i,j]开始搜索，不断分解为更小的状态[i-1,j]和[i,j-1]，递归函数包括以下的要素。

递归参数：状态[i,j]。
返回值：从[0,0]到[i,j]的最小路径和dp[i,j]。
终止条件：当 i = 0 且 j = 0 时，返回代价grid[0,0]。
剪枝：当i<0时或j<0时索引越界时，此时返回代价+∞，代表不可行。

实现代码如下所示：

# python 代码示例
def min_path_sum_dfs(grid, i, j) :if i == 0 and j == 0 :return grid[0][0]if i < 0 or j < 0 :return infup = min_path_sum_dfs(grid, i - 1, j)left = min_path_sum_dfs(grid, i, j - 1)return min(up, left) + grid[i][j]

// c++ 代码示例
int minPathSumDFS(vector<vector<int>> &grid, int i, int j)
{if (i == 0 && j == 0){return grid[0][0] ;}    if (i < 0 or j < 0){retunr INT_MAX ;}int up = minPathSumDFS(grid, i - 1, j) ;int left = minPathSumDFS(grid, i, j - 1) ;return min(up, left) + gird[i][j] ;
}

解析：

给出一个dp[2,1]为根节点的递归树，其中包含一些重叠子问题，其数量会随着网格grid的尺寸变大而急剧增多。

造成重叠子问题的原因：存在多条路径可以从左上角到达某一单元格。

每个状态都有向下和向右两种选择，从左上角走到右下角总共需要m+n-2步，所以最差的时间复杂度为O(2^(m+n))。这种计算方法并没有考虑网格的边界情况，当到达网格边界时只剩下一种选择，因此实际的路径会少一些。

方法二：记忆化搜索

引入一个与grid网格大小相同的记忆列表mem，用于记录各个子问题的解，并将重叠子问题进行剪枝。

代码示例：

// c++ 代码示例
def min_path_sum_dfs_mem(grid, mem, i, j) :if i == 0 and j == 0 :return grid[0][0]if i < 0 or j < 0 :return infif mem[i][j] != -1 :return mem[i][j]up = min_path_sum_dfs_mem(grid, mem, i - 1, j)left = min_path_sum_dfs_mem(grid, mem, i, j - 1)mem[i][j] = min(up, left) + grid[i][j]return mem[i][j]

// c++ 代码示例
int minPathSumDFSMem(vector<vector<int>> &grid, vector<vector<int>> &mem, int i, int j) {if (i == 0 && j == 0) {return grid[0][0] ;}if (i < 0 || j < 0) {return INT_MAX ;}if (mem[i][j] != -1) {return mem[i][j] ;}int up = minPathSumDFSMem(grid, mem, i - 1, j) ; int left = minPathSumDFSMem(grid, mem, i, j - 1) ;mem[i][j] = min(left, up) != INT_MAX ? min(left, up) + grid[i][j] : INT_MAX ;return mem[i][j] ;
}

解析：

在引入记忆化搜索之后，所有的子问题只需要计算一次，因此时间复杂度取决于状态总数，即网格尺寸O(m*n)

方法三：动态规划

基于迭代实现动态规划，代码如下所示：

# pyhton 代码示例
def min_path_sum_dp(grid) :n, m = len(grid), len(grid[0])dp = [ [0] * m for _ in range(n)]dp[0][0] = grid[0][0]for j in range(1, m) :dp[0][j] = dp[0][j - 1] + grid[0][j]for i in range(1, n) :dp[i][0] = dp[i - 1][0] + grid[i][0]for i in range(1, n) :for j in range(1, m) :dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + gird[i][j]return dp[n - 1][m - 1]

int minPathSumDP(vector<vector<int>> &grid) {int n = grid.size(), m = grid[0].size();vector<vector<int>> dp(n, vector<int>(m));dp[0][0] = grid[0][0];for (int j = 1; j < m; j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}for (int i = 1; i < n; i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];}}return dp[n - 1][m - 1];
}

动态规划的过程如下所示：便利了整个网络，因此时间复杂度为O(m*n)。

数组的dp的大小也为m * n ,因此空间复杂度为O(m*n)。

空间优化

由于每个格子只与左边和上边的格子有关，我们可以只用一个单行数组来实现dp表。

关键：数组dp只能表示一行的状态，我们无法提前初始化首行的状态，而是在遍历每行时更新它。

代码如下：

# python 代码示例def min_path_sum_dp_comp(grid : list[list[int]]) -> int :n, m = len(grid), len(grid[0])dp = [0] * mdp[0] = grid[0][0]for j in range(1, m) :dp[j] = dp[j - 1] + grid[0][j]for i in range(1, n) :dp[0] = dp[0] + grid[i][0]for j in range(1, m) :dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]return dp[m - 1]

// c++ 代码示例
int minPathSumDPComp(vector<vector<int>> &grid)
{int n = grid.size(), m = grid[0].size() ;vector<int> dp(m) ;dp[0] = grid[0][0] ;for (int j = 1 ; j < m ; j++){dp[j] = dp[j - 1] + gird[0][j] ;}for (int i = 1 ; i < n ; i++){dp[0] = dp[0] + grid[i][0] ;for (int j = 1 ; j < m ; j++){dp[j] = min(dp[j - 1], dp[j]) + grid[i][j] ;}}return dp[m- 1] ;
}