题解 | #变向#_牛客博客

思路：

题目的主要信息：

$3$ 行 $n$ 列的矩阵，起始位置第一列任意行
每到一个矩阵一格时会获得该格子的金币
当位于第行第列时，他下一步最多可能有三种选择：
1. 不花费金币跑到第i行第j+1列
2. 花费 $m_j$ 的金币跑到第 $i-1$ 行第 $j+1$ 列（如果 $i=1$ 则不可以这么跑）
3. 花费 $m_j$ 的金币跑到第 $i+1$ 行第 $j+1$ 列（如果 $i=3$ 则不可以这么跑）
初始金币无限，求能够获得的最多金币，即获得减去消耗

方法一：动态规划
具体做法：
可以用动态规划解决这类问题，首先假设 $dp[i][j]$ 就是第 $i$ 行第 $j$ 列能够获得最大金币数，其中 $i=0、1、2$ ，于是对于第 $0$ 行，它的前一个可以来自于第 $0$ 行的 $j-1$ 列或者是第 $1$ 行的 $j-1$ 列，如果是第 $1$ 行需要减去它在 $j-1$ 列时换行的花费。因此有如下转移方程：
图片说明

class Solution {
public:
    int solve(int n, vector<int>& a1, vector<int>& a2, vector<int>& a3, vector<int>& m) {
        vector<vector<int>> dp(3, vector<int>(n, 0)); //dp[i][j]表示第i行第j列能够获得到最大金币
        //边界第一列
        dp[0][0] = a1[0];
        dp[1][0] = a2[0];
        dp[2][0] = a3[0];
        for(int i = 1; i < n; i++){ //从第一列往后加
            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - m[i - 1]) + a1[i];
            dp[1][i] = max(max(dp[0][i - 1] - m[i - 1], dp[2][i - 1] - m[i - 1]), dp[1][i - 1]) + a2[i];
            dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] - m[i - 1]) + a3[i];
        }
        return  max(max(dp[0][n - 1], dp[1][n - 1]), dp[2][n - 1]); //选择最大值，因为初位置可选
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历一次，循环 $n$ 次
空间复杂度： $O(n)$ ，辅助数组dp相当于三个一维数组

方法二：递归+空间记忆
具体做法：
上述动态规划我们也可以用递归来做。
依照上述公式，对于每一行 $n-1$ 的问题可以用 $n-2$ 的子问题来相加得到，只要不断递归向下，就可以求得顶层的问题。为了防止重复计算递归树底层的元素，我们使用一个数组dp记录第一次递归得到的值，后续再遇到直接取数组即可。
如图所示，图中红框就是递归过一个点后剩余的子问题。
图片说明

class Solution {
public:
    //k为行号，n为列号
    int recursion(int k, int n, vector<int>& a1, vector<int>& a2, vector<int>& a3, vector<int>& m, vector<vector<int>>& dp){
        if(n == 0){  
            dp[0][0] = a1[0];
            dp[1][0] = a2[0];
            dp[2][0] = a3[0];
            return dp[k][n];
        }
        if(dp[k][n] == INT_MIN){ //如果数组没有记录再递归
            if(k == 0){
                dp[0][n] = max(recursion(0, n - 1, a1, a2, a3, m, dp), recursion(1, n - 1, a1, a2, a3, m, dp) - m[n - 1]) + a1[n];
            }
            else if(k == 2){
                dp[2][n] = max(recursion(2, n - 1, a1, a2, a3, m, dp), recursion(1, n - 1, a1, a2, a3, m, dp) - m[n - 1]) + a3[n];
            }
            else{
                dp[1][n] = max(max(recursion(0, n - 1, a1, a2, a3, m, dp), recursion(2, n - 1, a1, a2, a3, m, dp)) - m[n - 1], recursion(1, n - 1, a1, a2, a3, m, dp)) + a2[n];
            }
        }
        return dp[k][n];
    }
    int solve(int n, vector<int>& a1, vector<int>& a2, vector<int>& a3, vector<int>& m) {
        vector<vector<int>> dp(3, vector<int>(n, INT_MIN)); //dp[i][j]表示第i行第j列能够获得到最大金币
        int a = recursion(0, n - 1, a1, a2, a3, m, dp); //不同的起始位置递归
        int b = recursion(1, n - 1, a1, a2, a3, m, dp);
        int c = recursion(2, n - 1, a1, a2, a3, m, dp);
        return  max(max(a, b), c); //取其最大值
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，三次调用递归，相当于填满dp矩阵，而dp矩阵相当于三个一维 $n$ 长度的数组
空间复杂度： $O(n)$ ，递归栈最大深度和辅助数组dp