核心思想
- 拆分子问题，记住过往，减少重复计算。
就下面9道题而言，个人总结出来的解题经验主要在于：
- 明确状态量；
- 确定状态转移方程；
- 确定初始状态或初始值以及边界条件；
1. 不同路径
题目描述：一个 mxn 的棋盘，每次只能向右走或向下走，问到达右下角有多少种走法？
状态转移方程: f(m,n) = f(m-1,n)+f(m,n-1),其中 f(0,n) = 1,f(m,0) = 1;
class Solution {
public:
int uniquePaths(int m, int n) {
std::vector<int> dp(n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
dp[j] = 1; // f(0,n) 与 f(m,0) 都为 1
} else {
dp[j] += dp[j - 1]; // f(m,n) = f(m-1,n)+f(m,n-1) 此处将二维数组优化为了1维数组
}
}
}
return dp[n - 1];
}
};2. 不同路径 II
题目描述：一个 mxn 的棋盘，每次只能向右走或向下走，但是现在棋盘上有了障碍物，arr[i,j]=1 表示障碍物，arr[i,j]=0 表示可通行，问到达右下角有多少种走法？
状态转移方程: f(m,n) = f(m-1,n)+f(m,n-1), f(m,0) = f(m-1,0)、f(0,n) = f(0,n-1)
如果 arr[i,j] == 1 则 f(m,n) = 0
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
std::vector<int> dp(n);
dp[0] = 1; // 初始化默认为 1
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 存在障碍物，则此格为 0
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
continue;
}
if (i > 0 && j > 0) {
dp[j] += dp[j - 1]; // f(m,n) = f(m-1,n)+f(m,n-1)
} else if (i > 0) {
dp[j] = dp[0]; // j = 0 则只能向下走，f(m,n) = f(m-1,0)
} else if (j > 0) {
dp[j] = dp[j - 1]; // i = 0 则只能向右走，f(m,n) = f(0,n-1)
}
}
}
return dp[n - 1];
}
};3. 最小路径和
题目描述：一个包含非负整数的 mxn 的网格，每次只能向右走或向下走，找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
状态转移方程：
f(m,n) = min(f(m-1,n), f(m,n-1)) + arr[m,n]
f(0,n) = f(0,n-1) + arr[0,n]
f(m,0) = f(m-1,0) + arr[m,0]
class Solution {
public:
int minPathSum(vector<vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
std::vector<int> dp(n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i > 0 && j > 0) {
// f(m,n) = min(f(m-1,n), f(m,n-1)) + arr[m,n]
dp[j] = std::min(dp[j - 1], dp[j]) + grid[i][j];
} else if (i > 0) {
// j = 0 则只能向下走，f(m,n) = f(m-1,0) + arr[m,n]
dp[j] = dp[j] + grid[i][j];
} else if (j > 0) {
// i = 0 则只能向右走，f(m,n) = f(0,n-1) + arr[m,n]
dp[j] = dp[j - 1] + grid[i][j];
} else {
// i j 都为0，则 f(m,n) = arr[0,0]
dp[j] = grid[i][j];
}
}
}
return dp[n - 1];
}
};4. 三角形最小路径和
题目描述：现在将网格变为三角形，求出最小路径和？图解转换：
2 2
3 4 --------> 3 4
6 5 7 transfrom 6 5 7
4 1 8 3 4 1 8 3 也就是说，当前元素可以连接左上方的元素或上方元素；所以状态方程：
f(i,j) = min(f(i-1,j-1), f(i-1,j)) + arr(i, j)
只能连接上方元素：f(i,0) = f(i-1,0) + arr(i, j)
只能连接左上方元素：f(i,j) = f(i-1,j-1) + arr(i, j)
注意：更新 f(i,j) 时从右向左更新
class Solution {
public:
int minimumTotal(vector<vector<int>> &triangle) {
int n = triangle[triangle.size() - 1].size();
std::vector<int> dp(n);
// 本题在仅用一维数组存储时更新dp要从右向左，从左向右的话存在覆盖现象；
for (int i = 0; i < n; ++i) {
for (int j = triangle[i].size() - 1; j >= 0; --j) {
if (i > 0 && j > 0 && j < triangle[i].size() - 1) {
// 可以连接正上方与左上方元素，f(i,j) = min(f(i-1,j-1), f(i-1,j)) + arr(i, j)
dp[j] = std::min(dp[j - 1], dp[j]) + triangle[i][j];
} else if (i > 0 && j == 0) {
// 只能连接正上方元素，f(i,0) = f(i-1,0) + arr(i, j)
dp[j] = dp[j] + triangle[i][j];
} else if (i > 0 && j > 0 && j == triangle[i].size() - 1) {
// 只能连接左上方元素，f(i,j) = f(i-1,j-1) + arr(i, j)
// 从左向右的话，这里的[j-1]不再是上一层的了，是本层更新后的值了，就产生了覆盖
dp[j] = dp[j - 1] + triangle[i][j];
} else {
// i j 都为0，则 f(m,n) = arr(0, 0)
dp[j] = triangle[i][j];
}
}
}
return *std::min_element(dp.begin(), dp.end());
}
};5. 下降路径最小和
题目描述：方形网格（nxn），找出下降路径的最小和。下降路径指当前元素可以连接左上方、正上方、右上方三个元素中的一个。状态转移方程：
f(i,j) = min(f(i-1,j-1), f(i-1,j), f(i-1,j+1)) + arr[i,j]
最左侧(j=0)：f(i,0) = min(f(i-1,0), f(i-1,1)) + arr[i,j]
最右侧(j=n)：f(i,n) = min(f(i-1,n-1), f(i-1,n)) + arr[i,j]
class Solution {
public:
int minFallingPathSum(vector<vector<int>> &matrix) {
int n = matrix.size();
/*
* 此处没有再用一维数组，因为一维数组存在覆盖现象，需要用一个变量去记录当前状态左侧未更新前的值。
* 也没有在原数组上直接更新数值，是因为传参为引用，为了避免修改原始数据，所以用了一个二维数组。
*/
std::vector<std::vector<int>> dp(2, std::vector<int>(n));
for (int i = 0; i < n; ++i) {
// int pre = 0;
for (int j = 0; j < n; ++j) {
if (i > 0 && j > 0 && j < n - 1) {
// f(i,j) = min(f(i-1,j-1), f(i-1,j), f(i-1,j+1)) + arr[i,j]
dp[i % 2][j] = std::min(dp[(i - 1) % 2][j - 1], std::min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j + 1])) + matrix[i][j];
} else if (i > 0 && j == 0) {
// 最左侧(j=0)：f(i,0) = min(f(i-1,0), f(i-1,1)) + arr[i,j]
dp[i % 2][j] = std::min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j + 1]) + matrix[i][j];
} else if (i > 0 && j == n - 1) {
// 最右侧(j=n)：f(i,n) = min(f(i-1,n-1), f(i-1,n)) + arr[i,j]
dp[i % 2][j] = std::min(dp[(i - 1) % 2][j - 1], dp[(i - 1) % 2][j]) + matrix[i][j];
} else {
dp[i % 2][j] = matrix[i][j];
}
// pre = dp[j]; 此处记录左侧的状态值，当下次循环时dp[j-1]用pre替代即可
}
}
return *std::min_element(dp[(n + 1) % 2].begin(), dp[(n + 1) % 2].end());
}
};6. 下降路径最小和 II
题目描述：方形网格（nxn），找出 非零偏移下降路径 的最小和。非零偏移下降路径指从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列 。状态转移方程：
f(i,j) = min(f(i-1,0), …, f(i-1,j-1), f(i-1,j+1), …, f(i-1,n)) + arr[i,j]
最左侧(j=0)：f(i,0) = min(f(i-1,1), …, f(i-1,n)) + arr[i,j]
最右侧(j=n)：f(i,n) = min(f(i-1,0), …, f(i-1,n-1)) + arr[i,j]
class Solution {
public:
int minFallingPathSum(vector<vector<int>> &grid) {
int n = grid.size();
std::vector<std::vector<int>> dp(2, std::vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i > 0 && j > 0 && j < n - 1) {
// f(i,j) = min(f(i-1,0), …, f(i-1,j-1), f(i-1,j+1), …, f(i-1,n)) + arr[i,j]
dp[i % 2][j] = std::min(*std::min_element(dp[(i + 1) % 2].begin(), dp[(i + 1) % 2].begin() + j),
*std::min_element(dp[(i + 1) % 2].begin() + j + 1, dp[(i + 1) % 2].begin() + n))
+ grid[i][j];
} else if (i > 0 && j == 0) {
// 最左侧(j=0)：f(i,0) = min(f(i-1,1), …, f(i-1,n)) + arr[i,j]
dp[i % 2][j] = *std::min_element(dp[(i + 1) % 2].begin() + 1, dp[(i + 1) % 2].begin() + n) + grid[i][j];
} else if (i > 0 && j == n - 1) {
// 最右侧(j=n)：f(i,n) = min(f(i-1,0), …, f(i-1,n-1)) + arr[i,j]
dp[i % 2][j] = *std::min_element(dp[(i + 1) % 2].begin(), dp[(i + 1) % 2].begin() + n - 1) + grid[i][j];
} else {
dp[i % 2][j] = grid[i][j];
}
}
}
return *std::min_element(dp[(n + 1) % 2].begin(), dp[(n + 1) % 2].end());
}
};7. 统计所有可行路径
题目描述：给你一个互不相同的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量。
每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。
注意：fuel 任何时刻都不能为负，且可以经过任意城市超过一次（包括 start 和 finish ）。
请返回从 start 到 finish 所有可能路径的数目。
思路一：
递归+回溯：没有缓存重复运算，过不了复杂度。
void dfs(vector<int> &locations, int start, int finish, int fuel, int &res) {
if (fuel < 0) {
return;
} else if (fuel >= 0 && start == finish) {
res += 1;
}
for (int i = 0; i < locations.size(); i++) {
if (i == start) { continue; }
fuel -= std::abs(locations[i] - locations[start]);
dfs(locations, i, finish, fuel, res);
fuel += std::abs(locations[i] - locations[start]);
}
}
int countRoutes(vector<int> &locations, int start, int finish, int fuel) {
int res = 0;
dfs(locations, start, finish, fuel, res);
return res;
}思路二：
记忆化搜索：状态量有起始位置与剩余燃料，用dp[i, j]表示当前位置与剩余燃料
int dfs(vector<int> &locations, int start, int finish, int fuel, vector<vector<int>> &memo) {
if (fuel < 0) {
return 0;
}
// 如果当前这个位置，当前剩余燃料值出现过，直接返回数组中记录的值
if (memo[start][fuel] != -1) {
return memo[start][fuel];
}
// 起始位置==结束位置，表示走到了，res = 1;
int res = (start == finish) ? 1 : 0;
for (int i = 0; i < locations.size(); ++i) {
if (i != start) {
int cost = std::abs(locations[i] - locations[start]);
res = (res + dfs(locations, i, finish, fuel - cost, memo)) % 1000000007;
}
}
// 记录当前这种状态的结果
memo[start][fuel] = res;
return res;
}
int countRoutes(vector<int> &locations, int start, int finish, int fuel) {
int n = locations.size();
vector<vector<int>> memo(n, vector<int>(fuel + 1, -1)); // 初始化状态表，默认用-1填充
return dfs(locations, start, finish, fuel, memo);
}思路三：
动态规划：和记忆化搜索相同，状态还是当前位置与油量；状态转移方程为：
dp[pos, fuel] = dp[pos, fuel] + dp[d_pos, d_fuel]
int countRoutes(vector<int> &locations, int start, int finish, int fuel) {
int n = locations.size();
// 状态量：当前城市位置、所剩余的油量，dp[pos, fuel] 表示在pos这个城市油量为fuel时的路径数
std::vector<std::vector<int>> dp(n, std::vector<int>(fuel + 1));
// dp数组初始化，当前位置就是终点位置时，
for (int i = 0; i < fuel + 1; ++i) { dp[finish][i] = 1; }
// 状态转移方程：dp[pos, fuel] = dp[pos, fuel] + dp[d_pos, d_fuel]
// 表示从 d_pos 移动到 pos，油量从 d_fuel 下降到 fuel
for (int i = 0; i < fuel + 1; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
if (j == k) { continue; }
int need = std::abs(locations[k] - locations[j]);
if (i >= need) {
dp[j][i] += dp[k][i - need];
dp[j][i] %= 1000000007;
}
}
}
}
return dp[start][fuel];
}8. 出界的路径数
题目描述：给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。
动态规划：
- 状态量：当前位置、最大移动次数
- 状态转移方程：
dp[i,j][step] = dp[i-1,j][step-1]+dp[i,j+1][step-1]+dp[i+1,j][step-1]+dp[i,j-1][step-1]；当 step 为 0 时，dp[i,j][step] = 0;
void dp_init(int i, int j, std::vector<std::vector<int>> &dp, int col) {
int maxStep = dp[0].size();
int idx = idx_encoder(i, j, col);
for (int i = 1; i < maxStep; ++i) {
dp[idx][i]++;
}
}
int idx_encoder(int i, int j, int col) {
int idx = i * col + j;
return idx;
}
std::pair<int, int> idx_decoder(int idx, int col) {
int x = idx / col;
int y = idx % col;
return std::make_pair(x, y);
}
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
// 将二维矩阵拉伸成一维矩阵，这样第一维表示位置，第二维表示最大移动次数
// 创建dp数组，行表示每个格子的id，列表示移动次数,列数为 maxMove+1;
std::vector<std::vector<int>> dp(m * n, std::vector<int>(maxMove + 1));
// 初始化dp数组，四个角与四条边上的元素赋初值
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0) { dp_init(i, j, dp, n); }
if (i == m - 1) { dp_init(i, j, dp, n); }
if (j == 0) { dp_init(i, j, dp, n); }
if (j == n - 1) { dp_init(i, j, dp, n); }
}
}
// 定义转移方向：上左下右
std::vector<std::pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
/*
* 状态转移方程：
* dp[i,j][step] = dp[i-1,j][step-1]+dp[i,j+1][step-1]+dp[i+1,j][step-1]+dp[i,j-1][step-1]
* 如果 step 为 0 时，dp[i,j][step] = 0;
*/
for (int step = 1; step <= maxMove; ++step) {
for (int idx = 0; idx < m * n; ++idx) {
// idx 反解
auto xy = idx_decoder(idx, n);
int x = xy.first, y = xy.second;
for (auto direction : directions) {
// 计算向 direction 方向移动一步后的 xy 坐标
int prev_x = x + direction.first, prev_y = y + direction.second;
// xy 坐标编码 idx
int pre_idx = idx_encoder(prev_x, prev_y, n);
if (prev_x >= 0 && prev_x < m && prev_y >= 0 && prev_y < n) {
dp[idx][step] += dp[pre_idx][step - 1];
dp[idx][step] %= 1000000007;
}
}
}
}
return dp[idx_encoder(startRow, startColumn, n)][maxMove];
}9. 最大得分的路径数目
题目描述：给你一个正方形字符数组 board ，你从数组最右下方的字符 ‘S’ 出发。你的目标是到达数组最左上角的字符 ‘E’ ，数组剩余的部分为数字字符 1, 2, …, 9 或者障碍 ‘X’。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
一条路径的 「得分」 定义为：路径上所有数字的和。
请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。
如果没有任何路径可以到达终点，请返回 [0, 0] 。
动态规划：
状态量：当前位置，最大分数
最大分数：
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + board[i][j];最大路径数：当三个方向有相同的最大分数时，路径数是两个方向的和，路径dp数组初始化为 1；
dp_road[i][j] = { (dp_road[i - 1][j] + dp_road[i][j - 1] + dp_road[i - 1][j - 1]) % 1000000007 if dp[i - 1][j] == dp[i][j - 1] == dp[i - 1[j - 1] }
void update(int n, int i, int j, int x, int y, std::vector<std::vector<std::pair<int, int>>> &dp) {
// 边界处理，处理越界的情况，还需要考虑此路不通的情况，即[x,y]的最大分数为-1，表示不能通过xy对ij进行转移
if (x >= n || y >= n || dp[x][y].first == -1) {
return;
}
// 此时还没有通过board[i][j]的值更新dp[i][j].first的最大分数，所以dp[i][j].first表示的是右侧三个状态的最大分数
if (dp[i][j].first < dp[x][y].first) {
dp[i][j] = dp[x][y];
} else if (dp[i][j].first == dp[x][y].first) {
dp[i][j].second += dp[x][y].second;
dp[i][j].second %= 1000000007;
}
}
vector<int> pathsWithMaxScore(vector<string> &board) {
// 状态量：当前位置，最大分数
// dp[i][j] = max(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]) + board[i][j];
// 最大路径数：
// dp_road[i][j] = {
// (dp[i + 1][j] + dp[i][j + 1] + dp[i + 1][j + 1]) % 1000000007
// if dp[i + 1][j] == dp[i][j + 1] == dp[i + 1][j + 1]
// }
int n = board.size();
std::vector<std::vector<std::pair<int, int>>> dp(n, std::vector<std::pair<int, int>>(n, {-1, 0}));
dp[n - 1][n - 1] = {0, 1};
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
// 右下角的元素 'S' 跳过
if (i == n - 1 && j == n - 1) { continue; }
// 如果当前元素为 'X' 就跳过，当前格子的状态仍旧为初始值 {-1,0}
if (board[i][j] == 'X') { continue; }
// 状态转移，用右侧、右下侧、下侧的三个状态更新当前状态值
update(n, i, j, i, j + 1, dp); // 右侧
update(n, i, j, i + 1, j + 1, dp); // 右下侧
update(n, i, j, i + 1, j, dp); // 下侧
// 根据 board[i][j] 的值更新dp[i][j]的最大分数，此处要加上是否能到达判断；
// 如果 dp[i][j].first == -1 表示三个位置都不能到达当前位置，那么就不更新，还是初始值 {-1,0}
if (dp[i][j].first != -1) {
// 如果是第一个元素（左上角）那最大分数就不变
dp[i][j].first += (board[i][j] == 'E' ? 0 : board[i][j] - '0');
}
}
}
return dp[0][0].first == -1 ? vector<int>{0, 0} : vector<int>{dp[0][0].first, dp[0][0].second};
}
