DP+贪心
思路：
定义f(i,j)表示从左上角走到坐标(i，j)处能获得的最大奖励。
搜索所有从左上角走到右下角的路径，找到最优路径。
f(i,j)分三种情况：
第一列：f(i, 0) = f(i-1, 0) + board(i, 0)
如果处在第一列，那么由于是第一列，所以从起点走，它只可能是向下不断走的到的
第一行：f(0,j) = f(0, j - 1) + b(0, j)
如果处在第一行，那么由于是第一行，所以从起点走，它只可能是向右不断走得到的
其它位置：f(i, j) = max{f(i-1, j), f(i, j - 1)} + board(i, j)
最后返回右下角的值
class Bonus { public: int getMost(vector<vector<int> > board) { int x=board.size(); int y=board[0].size(); //vector<vector<int>> tot(x,vector<int>(y,0)); int tot[6][6]={0}; tot[0][0]=board[0][0]; for(int i=0;i<x;i++) { for(int j=0;j<y;j++) { if(i==0&&j==0) continue; else if(i==0) tot[i][j]=tot[i][j-1]+board[i][j]; else if(j==0) tot[i][j]=tot[i-1][j]+board[i][j]; else tot[i][j]=max(tot[i-1][j],tot[i][j-1])+board[i][j]; } } return tot[x-1][y-1]; } };
dfs迷宫问题（最短路径）
思路：
本题可用回溯法求解 具体步骤为：
1. 首先将当前点加入路径，并设置为已走
2. 判断当前点是否为出口，是则输出路径，保存结果；跳转到 4
3. 依次判断当前点的上、下、左、右四个点是否可走，如果可走则递归走该点
4. 当前点推出路径，设置为可走
#include<iostream> #include<vector> using namespace std; int ROW, COL; vector<vector<int>> maze; vector<vector<int>> path_tmp; //临时路劲 vector<vector<int>> path_best; //最佳路劲 void MazeTrack(int i, int j) { maze[i][j] = 1; //代表（i,j）已经走过 path_tmp.push_back({i, j}); //判断是否到达出口 if (i == ROW - 1 && j == COL - 1) { //寻找最短路劲 if (path_best.empty() || path_best.size() > path_tmp.size()) path_best = path_tmp; } //向右走 if (j + 1 < COL && maze[i][j + 1] == 0) MazeTrack(i, j + 1); //向左走 if (j - 1 >= 0 && maze[i][j - 1] == 0) MazeTrack(i, j - 1); //向上走 if (i - 1 >= 0 && maze[i - 1][j] == 0) MazeTrack(i - 1, j); //向下走 if (i + 1 < ROW && maze[i + 1][j] == 0) MazeTrack(i + 1, j); maze[i][j] = 0; //走不通，回溯 恢复路径 path_tmp.pop_back(); } int main() { cin >> ROW >> COL; maze = vector<vector<int>>(ROW, vector<int>(COL, 0)); //开辟迷宫空间 //首先输入迷宫 for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) cin >> maze[i][j]; } MazeTrack(0, 0); //从起始点（0，0）开始走 //输出路径 for (int i = 0; i < path_best.size(); ++i) { cout << "(" << path_best[i][0] << "," << path_best[i][1] << ")" << endl; } return 0; }
用pair对组优化
#include<bits/stdc++.h> using namespace std; int dirs[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1}; int n, m, grid[10][10]; vector<pair<int, int>> bestPath, path; void dfs(int x, int y) { grid[x][y] = 1; path.emplace_back(x, y); if (x == n - 1 && y == m - 1) // 到达终点 if (bestPath.empty() || path.size() < bestPath.size()) { bestPath = path; return; } for (auto &[dx, dy] : dirs) { int nx = x + dx, ny = y + dy; if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny]) continue; dfs(nx, ny); } path.pop_back(); // 还原状态 grid[x][y] = 0; } int main() { cin >> n >> m; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> grid[i][j]; dfs(0, 0); for (auto &[x, y] : bestPath) { printf("(%d,%d)\n", x, y); } return 0; }
