题解 | #流浪者与宝藏#

思路：

题目的主要信息：

x和y是位置坐标数组（位置可能会重复），a为其对应的金币数，k为钥匙数量
从(0，0)开始，每次行动时进入下一步行号列号都要至少加1，到达一个地方，需要用一把钥匙开启宝藏，获得金币
钥匙有限，求能够获得的最大金币数，同一个一个地方只能访问一次

可以利用贪心思想，用矩阵记录每个位置的最大金币数，每次开启宝藏的时候肯定选择开启那个地方的最大金币数的宝藏才能保证最多。

方法一：动态规划
具体做法：
后续对于每个位置，可以用动态规划。设 $f[i][j][t]$ 表示 $(x,y)(1<=x<=i,1<=y<=j)$ 范围内，剩余 $t$ 把钥匙时所能获得的最大收益，初始状态肯定是0.
图片说明
我们可以看到图中，对于固定的钥匙 $t$ ， $(5,5)$ 处的值可以等于其上或者其左的值，因为每次行列都要至少加1，因此同一行同一列就不变，取其最大值，即 $dp[i][j][t] = max(dp[i - 1][j][t], dp[i][j - 1][t])$ ；当然如果也可以取图中的左上角加上本身，因为行列都加了1，便可以开启自己这处的宝藏，同样我们要找的是三者的最大值，即运算完上述后再来： $dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t + 1] + c[i][j])$ ，当然，如果 $(5,5)$ 宝藏的金币数为0，我们也不用考虑后面这条了，因为 $dp[i][j][t]= dp[i - 1][j][t]$ ，它们是同一列。
写好一个 $i,j,t$ 的循环后，就得到了整个地图的最大收益， $dp[row][col][t]$ ，值得注意的是并不是打开的宝藏越多收益就一定高的情况，我们还要调用函数找到其最大收益。

class Solution {
public:
    int solve(int n, int k, vector<int>& x, vector<int>& y, vector<int>& a) {
        int row = *max_element(x.begin(), x.end());
        int col = *max_element(y.begin(), y.end()); //找到边界
        vector<vector<int>> c(row + 1, vector<int>(col + 1, 0)); //记录每个最大宝藏
        for(int i = 0; i < n; i++)
            c[x[i]][y[i]] = max(c[x[i]][y[i]], a[i]); //将每个地方金币最大数存入矩阵
        vector<vector<vector<int> > > dp(row + 1, vector<vector<int> >(col + 1, vector<int>(k, 0)));
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                for(int t = 0; t < k; t++){ //每次k把钥匙
                    dp[i][j][t] = max(dp[i - 1][j][t], dp[i][j - 1][t]);
                    if(c[i][j] != 0)
                        dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t + 1] + c[i][j]);
                }
            }
        }
        return *max_element(dp[row][col].begin(), dp[row][col].end()); //取最大
    }
};

复杂度分析：

时间复杂度： $O(max(x_i)*max(y_i)*k + n)$ ，三层循环：k把钥匙和矩阵的两个边长，外加外面的遍历和找最大值是一个 $O(n)$ 的循环
空间复杂度： $O(max(x_i)*max(y_i)*k)$ ，最大空间使用是dp矩阵，其中矩阵c较小故忽略

方法二：动态规划空间优化
具体做法：
注意到方法一，我们只使用到了第 $i$ 行和第 $i-1$ 行，因此我们可以用两个数组交替表示来节省空间。
同时，我们可以将k次循环提到最外层，每次找到使用一次钥匙后能够得到金币数，就不需要最后再找最大值，动态规划转移方程还是相同的。
图片说明

class Solution {
public:
    int solve(int n, int k, vector<int>& x, vector<int>& y, vector<int>& a) {
        int row = *max_element(x.begin(), x.end());
        int col = *max_element(y.begin(), y.end()); //找到边界
        vector<vector<int>> c(row + 1, vector<int>(col + 1, 0)); //记录每个最大宝藏
        for(int i = 0; i < n; i++)
            c[x[i]][y[i]] = max(c[x[i]][y[i]], a[i]); //将每个地方金币最大数存入矩阵
        vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
        for(int z = 0; z < k; z++){
            vector<vector<int>> dp1(row + 1, vector<int>(col + 1, 0)); //滚动优化空间
            for(int i = 1; i <= row ; i++)
                for(int j = 1; j <= col; j++)
                    dp1[i][j] = max(dp[i - 1][j - 1] + c[i][j], max(dp1[i - 1][j], dp1[i][j - 1]));
            dp = dp1; //数组滚动
        }
        return dp[row][col];
    }
};

复杂度分析：

时间复杂度： $O(max(x_i)*max(y_i)*k + n)$ ，三层循环：k把钥匙和矩阵的两个边长，外加外面的遍历和找最大值是一个 $O(n)$ 的循环
空间复杂度： $O(max(x_i)*max(y_i))$ ，最大空间使用是dp矩阵，其中矩阵c较小故忽略