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

题目描述
牛牛准备在一个3行n列的跑道上跑步。一开始牛牛可以自己选择位于(1,1)还是(2,1)还是(3,1)。

跑道的每一格都有一些金币，当牛牛跑到一个格子，他会获得这个格子的所有金币。

当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：

不花费金币跑到第i行第j+1列
花费mj的金币跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
花费mj的金币跑到第i+1行第j+1列（如果i=3则不可以这么跑）。
（牛牛是一个富豪，本身带了很多的金币，所以你不用担心他钱不够用）
现在告诉你所有格子的金币数量和每一列的金币花费，牛牛想知道他跑到第n列最多可以赚得多少金币（赚得金币=获得金币-消耗金币）

方法一：暴力求解

求解思路
对于本题目的求解，我们首先分析牛牛的位置起始位置，因为有三种，因此我们分为三种情况分别去考虑牛牛最多可以赚得多少金币。如果牛牛的位置在第一行，它可以选择往右走或者往上走，并且对于第二步、第三步也如此，但是不能够超过格子的边界。然后我们记录每一步之后的金币数量，这样便可以得到初始位置在第一行时牛牛可以得到多少金币。同理，我们可以对初始位置在第二行、第三行的结果，最终即可得到本问题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m)
    {
        int[][] A = new int[3][n]; // 虚拟一个格子
        A[0][0] = a1[0]; // 起始位置(1,1)
        A[1][0] = a2[0]; // 起始位置(2,1)
        A[2][0] = a3[0]; // 起始位置(3,1)
        for (int i = 1; i < n; i++)
        {
        A[0][i]=Math.max(A[0][i-1]+a1[i], A[1][i-1]-m[i-1]+a1[i]); // case 1
        A[1][i]=Math.max(Math.max(A[1][i-1]+a2[i],A[0][i-1]-m[i-1]+a2[i]), A[2][i-1]-m[i-1]+a2[i]); // case 2
        A[2][i]=Math.max(A[2][i-1]+a3[i], A[1][i-1]-m[i-1]+a3[i]); // case 3
        }
    return Math.max(A[0][n-1],Math.max(A[1][n-1], A[2][n-1])); // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用数组A[3][n],因此空间复杂度为 $O(N)$

方法二：优化思想求解

求解思路
对于方法一，我们对其进行优化改进。我们可以将不同行不同列的最多钱币数累加到数组中，然后减去开销，这样也可以得到牛牛最多可以赚得多少钱币。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m)
    {
        for(int i=1;i<n;i++)
        {
            a1[i]+=Math.max(a1[i-1],a2[i-1]-m[i-1]); // case 1
            a2[i]+=Math.max(a2[i-1],Math.max(a1[i-1]-m[i-1],a3[i-1]-m[i-1])); // case 2
            a3[i]+=Math.max(a3[i-1],a2[i-1]-m[i-1]); // case 3
        }
        return Math.max(a1[n-1],Math.max(a2[n-1],a3[n-1])); // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为 $O(1)$