剑指offer（专项突破版）14.4 矩阵路径问题
分析
可以用函数f（i，j）表示从格子的左上角坐标为（0，0）的位置出发到达坐标为（i，j）的位置的路径的数目。如果格子的大小为m×n，那么f（m-1，n-1）就是问题的解。
当i等于0时，机器人位于格子最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。因此，f（0，j）等于1，即机器人只有一种方法可以到达坐标为（0，j）的位置，即从（0，j-1）的位置向右走一步。
当j等于0时，机器人位于格子最左边的一列，机器人不可能从某个位置向右走一步到达一个列号j为0的位置。因此，f（i，0）等于1，即机器人只有一种方法可以到达坐标为（i，0）的位置，即从（i-1，0）的位置向下走一步。
当行号i、列号j都大于0时，机器人有两种方法可以到达坐标为（i，j）的位置。它既可以从坐标为（i-1，j）的位置向下走一步，也可以从坐标为（i，j-1）的位置向右走一步，因此，f（i，j）等于f（i-1，j）与f（i，j-1）之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
|
优化空间效率
可以进一步优化空间效率，只需要创建一个一维数组dp就可以。在计算f（i，j）时需要用到f（i-1，j）和f（i，j-1）的值。接下来在计算f（i，j+1）时需要用到f（i-1，j+1）和f（i，j）的值。在计算完f（i，j）之后，就不再需要f（i-1，j）的值。在二维表格中，f（i，j）和f（i-1，j）是上下相邻的两个位置。由于在用f（i-1，j）计算出f（i，j）之后就不再需要f（i-1，j），因此可以只用一个位置来保存f（i-1，j）和f（i，j）的值。这个位置在计算f（i，j）之前保存的是f（i-1，j）的值，计算f（i，j）之后保存的是f（i，j）的值。由于每个位置能够用来保存两个值，因此只需要一个一维数组就能保存表格中的两行。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
};
|
分析
用函数f（i，j）表示从格子的左上角坐标为（0，0）的位置（用grid[0][0]表示）出发到达坐标为（i，j）的位置（用grid[i][j]表示）的路径的数字之和的最小值。如果格子的大小为m×n，那么f（m-1，n-1）就是问题的解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
for(int j = 1; j < n; j++){
dp[0][j] = grid[0][j] + dp[0][j-1];
}
for(int i = 1; i < m; i++){
dp[i][0] = grid[i][0] + dp[i-1][0];
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
};
|
优化空间效率
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> dp(n);
dp[0] = grid[0][0];
for(int j = 1; j < n; j++){
dp[j] = grid[0][j] + dp[j-1];
}
for(int i = 1; i < m; i++){
dp[0] = grid[i][0] + dp[0];
for(int j = 1; j < n; j++){
dp[j] = min(dp[j], dp[j-1]) + grid[i][j];
}
}
return dp[n-1];
}
};
|
分析
同样用f(i,j)来表示走到位置(i,j)时最小的路径和。对于第一行可以直接初始化，第一列的，只能由f(i-1,0)得到，最后一列的，只能由f(i-1, j-1)得到，且j<=i。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
int n = triangle[m-1].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = triangle[0][0];
for(int i = 1; i < m; i++){
for(int j = 0; j <= i; j++){
if(j == 0){
dp[i][j] = dp[i-1][j] + triangle[i][j];
}
else if(j == i){
dp[i][j] = dp[i-1][j-1] + triangle[i][j];
}
else{
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
}
}
}
int res = dp[m-1][0];
for(int j = 1; j < n; j++){
res = min(res, dp[m-1][j]);
}
return res;
}
};
|
优化空间效率
假设在计算f（i，j）之前“dp[j]”中保存的是f（i-1，j）的值。在计算f（i，j）时需要f（i-1，j-1）和f（i-1，j）。在计算完f（i，j）之后能否用f（i，j）的值覆盖保存在“dp[j]”中的f（i-1，j）取决于是否还需要f（i-1，j）的值。如果每行按照从左到右的顺序，那么在计算完f（i，j）之后将计算f（i，j+1），而计算f（i，j+1）可能需要f（i-1，j）和f（i-1，j+1）的值，也就是f（i-1，j）的值在计算f（i，j+1）时可能会被用到，因此在计算完f（i，j）之后不能将f（i-1，j）的值丢掉。
但计算f（i，j）时并不依赖同一行左侧的f（i，j-1），因此并不一定要按照从左到右的顺序计算每行，按照从右到左的顺序计算也可以。如果按照从右到左的顺序，则先计算f（i，j），需要用到f（i-1，j-1）和f（i-1，j）。接下来计算f（i，j-1），需要用到f（i-1，j-1）和f（i-1，j-2）。计算f（i-1，j-1）并不需要用到f（i-1，j）。因此，按照从右到左的顺序在计算完f（i，j）之后，将f（i，j）的值保存到“dp[j]”中并替换f（i-1，j）的值，并且不会带来任何问题，因此f（i-1，j）的值以后就不再需要。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
int n = triangle[m-1].size();
vector<int> dp(n);
dp[0] = triangle[0][0];
for(int i = 1; i < m; i++){
for(int j = i; j >= 0; j--){
if(j == 0){
dp[j] += triangle[i][j];
}
else if(j == i){
dp[j] = dp[j-1] + triangle[i][j];
}
else{
dp[j] = min(dp[j-1], dp[j]) + triangle[i][j];
}
}
}
int res = dp[0];
for(int j = 1; j < n; j++){
res = min(res, dp[j]);
}
return res;
}
};
|
总结
矩阵路径是一类常见的可以用动态规划来解决的问题。这类问题通常输入的是一个二维的格子，一个机器人按照一定的规则从格子的某个位置走到另一个位置，要求计算路径的条数或找出最优路径。
矩阵路径相关问题的状态方程通常有两个参数，即f（i，j）的两个参数i、j通常是机器人当前到达的坐标。需要根据路径的特点找出到达坐标（i，j）之前的位置，通常是坐标（i-1，j-1）、（i-1，j）、（i，j-1）中的一个或多个。相应地，状态转移方程就是找出f（i，j）与f（i-1，j-1）、f（i-1，j）或f（i，j-1）的关系。
可以根据状态转移方程写出递归代码，但值得注意的是一定要将f（i，j）的计算结果用一个二维数组缓存，以避免不必要的重复计算。也可以将计算所有f（i，j）看成填充二维表格的过程，相应地，可以创建一个二维数组并逐一计算每个元素的值。通常，矩阵路径相关问题的代码都可以优化空间效率，用一个一维数组就能保存所有必需的数据。