1219.黄金矿工
你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

示例 1：

输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释：
[[0,6,0],
[5,8,7],
[0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。
示例 2：

输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
解释：
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

提示：

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格中有黄金。

一开始我就是想的递归加回溯
但是我嫌麻烦，就用了值传递

class Solution {
private:vector<vector<int>> _grid;int getGold(int i, int j, vector<vector<int>> flagCache, int totalGold){if(i<0||j<0)return totalGold;if(i>=_grid.size())return totalGold;if(j>=_grid[i].size())return totalGold;if(_grid[i][j] == 0||flagCache[i][j] == 1)return totalGold;flagCache[i][j] = 1;vector<int> goldNumCache;goldNumCache.push_back(getGold(i-1,j,flagCache,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i+1,j,flagCache,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i,j-1,flagCache,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i,j+1,flagCache,totalGold + _grid[i][j]));sort(goldNumCache.begin(),goldNumCache.end());return goldNumCache.back();}
public:int getMaximumGold(vector<vector<int>>& grid) {_grid = grid;vector<vector<int>> _flag = vector<vector<int>>(grid.size());for(int i=0;i<grid.size();i++)_flag[i] = vector<int>(grid[i].size());vector<int> goldNum;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[i].size();j++){goldNum.push_back(getGold(i,j,_flag,0));}}sort(goldNum.begin(),goldNum.end());return goldNum.back();}
};

改成引用传递之后我本来还想着在递归调用函数之后回溯的

int getGold(int i, int j, int totalGold){if(i<0||j<0)return totalGold;if(i>=_grid.size())return totalGold;if(j>=_grid[i].size())return totalGold;if(_grid[i][j] == 0||_flag[i][j] == 1)return totalGold;_flag[i][j] = 1;vector<int> goldNumCache;// 递归goldNumCache.push_back(getGold(i-1,j,totalGold + _grid[i][j]));// 回溯if(goldNumCache.back() != totalGold + _grid[i][j])_flag[i-1][j] = 0;// 递归goldNumCache.push_back(getGold(i+1,j,totalGold + _grid[i][j]));// 回溯if(goldNumCache.back() != totalGold + _grid[i][j])_flag[i+1][j] = 0;// 递归goldNumCache.push_back(getGold(i,j-1,totalGold + _grid[i][j]));// 回溯if(goldNumCache.back() != totalGold + _grid[i][j])_flag[i][j-1] = 0;// 递归goldNumCache.push_back(getGold(i,j+1,totalGold + _grid[i][j]));// 回溯if(goldNumCache.back() != totalGold + _grid[i][j])_flag[i][j+1] = 0;sort(goldNumCache.begin(),goldNumCache.end());return goldNumCache.back();}

然后这样就错了……
我还在想哪里错了……但是我突然发现其实可以不用想这个了，它本身就麻烦
本来最简单的应该是在返回函数的时候回溯
就，只管自己的状态，这个原则，要遵守
而且确实可以允许这样做，我回溯在递归调用之后就是合理的

int getGold(int i, int j, int totalGold){if(i<0||j<0)return totalGold;if(i>=_grid.size())return totalGold;if(j>=_grid[i].size())return totalGold;if(_grid[i][j] == 0||_flag[i][j] == 1)return totalGold;_flag[i][j] = 1;vector<int> goldNumCache;// 递归goldNumCache.push_back(getGold(i-1,j,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i+1,j,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i,j-1,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i,j+1,totalGold + _grid[i][j]));sort(goldNumCache.begin(),goldNumCache.end());_flag[i][j] = 0;return goldNumCache.back();}

最终代码：

class Solution {
private:vector<vector<int>> _grid;vector<vector<int>> _flag;int getGold(int i, int j, int totalGold){if(i<0||j<0)return totalGold;if(i>=_grid.size())return totalGold;if(j>=_grid[i].size())return totalGold;if(_grid[i][j] == 0||_flag[i][j] == 1)return totalGold;_flag[i][j] = 1;vector<int> goldNumCache;// 递归goldNumCache.push_back(getGold(i-1,j,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i+1,j,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i,j-1,totalGold + _grid[i][j]));goldNumCache.push_back(getGold(i,j+1,totalGold + _grid[i][j]));sort(goldNumCache.begin(),goldNumCache.end());_flag[i][j] = 0;return goldNumCache.back();}
public:int getMaximumGold(vector<vector<int>>& grid) {_grid = grid;_flag = vector<vector<int>>(grid.size());for(int i=0;i<grid.size();i++)_flag[i] = vector<int>(grid[i].size());vector<int> goldNum;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[i].size();j++){goldNum.push_back(getGold(i,j,0));}}sort(goldNum.begin(),goldNum.end());return goldNum.back();}
};

还是超时了……不懂为啥……
看了一下别人的题解，感觉跟我的一样啊

别人不用 flag，用 grid 置 0 代替，我试试

class Solution {
private:vector<vector<int>> _grid;int getGold(int i, int j, int totalGold){if(i<0||j<0)return totalGold;if(i>=_grid.size())return totalGold;if(j>=_grid[i].size())return totalGold;if(_grid[i][j] == 0)return totalGold;int goldCache = _grid[i][j];_grid[i][j] = 0;vector<int> goldNumCache;// 递归goldNumCache.push_back(getGold(i-1,j,totalGold + goldCache));goldNumCache.push_back(getGold(i+1,j,totalGold + goldCache));goldNumCache.push_back(getGold(i,j-1,totalGold + goldCache));goldNumCache.push_back(getGold(i,j+1,totalGold + goldCache));sort(goldNumCache.begin(),goldNumCache.end());_grid[i][j] = goldCache;return goldNumCache.back();}
public:int getMaximumGold(vector<vector<int>>& grid) {_grid = grid;vector<int> goldNum;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[i].size();j++){goldNum.push_back(getGold(i,j,0));}}sort(goldNum.begin(),goldNum.end());return goldNum.back();}
};

还是超时了……思考……
让我再看看别人的题解

别人是先判断接下来要走的格子能不能走，然后再调用函数
我是先调用函数然后再判断自己的状态
我记得好像是调用函数也是要耗费时间的，所以才有内联这个东西
再让我试试

class Solution {
private:static constexpr int delta[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public:int getMaximumGold(vector<vector<int>>& grid) {function<int(int,int,int)> getGold = [&](int x, int y, int totalGold){vector<int> totalGoldCache;int goldCache = grid[x][y];grid[x][y] = 0;// 递归for(int i=0;i<4;i++){int nx = x + delta[i][0];int ny = y + delta[i][1];if((nx >= 0) && (ny >= 0) && (nx < grid.size()))if(ny < grid[nx].size())if(grid[nx][ny] != 0)totalGoldCache.push_back(getGold(nx, ny, totalGold + goldCache));}sort(totalGoldCache.begin(), totalGoldCache.end());grid[x][y] = goldCache;return totalGoldCache.back();};vector<int> goldNum;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[i].size();j++){if(grid[i][j] != 0)goldNum.push_back(getGold(i,j,0));}}sort(goldNum.begin(),goldNum.end());return goldNum.back();}
};

这个会出错……因为取 vector 的 back 的时候不一定有值
还需要预先加上一个默认的值

class Solution {
private:static constexpr int delta[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public:int getMaximumGold(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();function<int(int,int,int)> getGold = [&](int x, int y, int totalGold){vector<int> totalGoldCache;int goldCache = grid[x][y];grid[x][y] = 0;// 递归for(int i=0;i<4;i++){int nx = x + delta[i][0];int ny = y + delta[i][1];if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0)totalGoldCache.push_back(getGold(nx, ny, totalGold + goldCache));}totalGoldCache.push_back(totalGold + goldCache);sort(totalGoldCache.begin(), totalGoldCache.end());grid[x][y] = goldCache;return totalGoldCache.back();};vector<int> totalGoldCache2;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[i].size();j++){if(grid[i][j] != 0)totalGoldCache2.push_back(getGold(i,j,0));}}totalGoldCache2.push_back(0);sort(totalGoldCache2.begin(),totalGoldCache2.end());return totalGoldCache2.back();}
};

这样就好了