目录
问题判断:
总的来说，如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。然而，我们很难从问题的描述中直接提取出这些特征，因此通常需要放宽条件，首先需要观察问题适不适合使用回溯（穷举）解决。
适合用回溯解决的问题通常满足“决策树模型”，对于问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。
换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯解决。
在此基础上，动态规划问题还有一些判断的“加分项”。
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 inf
up = 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 inf
if 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] * m
dp[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] ;
}
