变向

描述
牛牛准备在一个3行n列的跑道上跑步。一开始牛牛可以自己选择位于(1,1)还是(2,1)还是(3,1)，跑道的每一格都有一些金币，当牛牛跑到一个格子，他会获得这个格子的所有金币。
当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：
1. 不花费金币跑到第i行第j+1列
2. 花费m_j的金币跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
3. 花费m_j的金币跑到第i+1行第j+1列（如果i=3则不可以这么跑）。
（牛牛是一个富豪，本身带了很多的金币，所以你不用担心他钱不够用）
现在告诉你所有格子的金币数量和每一列的金币花费，牛牛想知道他跑到第n列最多可以赚得多少金币（赚得金币=获得金币-消耗金币）
示例
输入：3,[1,9,3],[6,4,6],[1,1,5],[3,2,1]
返回值：16
说明：一开始牛牛选择位于第2行第1列，拿到6个金币。然后牛牛花3金币到第1行的2列拿到9个金币，最后牛牛花费2金币到第2行第3列。总共获得21金币，消耗5金币。赚得16金币。

方法一

思路分析

    由于牛牛的起始位置有三种选择，因此对于每一种起始位置构建辅助数组l[i][j]表示当前位置下第i行第j列所赚得的金币数。要想到达最后一列，那么其子问题为达到n-1列，不断的将问题放小，因此辅助数组从小问题出发，记录到达下一列的所赚的最多金币数，最后输出l[0][n-1]或者l[1][n-1]或者l[2][n-1]中的最大值，即第一种起始位置到达最后一列的金币数。根据题目写出其状态转移方程：
  • 始终在第一行：$l[0][i]$位置的金币数可能为$l[0][i-1]$直接向右侧走一列到达即$l[0][i]=l[0][i-1]+a1[i]$，或者从l[1][i-1]向上走一格后向右走一格，此时获得的金币为$a1[i]$，损耗的金币为$m[i-1]$，此时$l[0][i]=l[1][i-1]+a1[i]-m[i-1]$。因此获得转移方程：$l[0][i]=max(l[0][i-1]+a1[i]，l[1][i-1]+a1[i]-m[i-1])$

  • 始终在第二行：$l[1][i]$位置的金币数可能为$l[1][i-1]$直接向右侧走一列到达即$l[1][i]=l[1][i-1]+a2[i]$，或者从$l[2][i-1]$向上走一格后向右走一格，此时获得的金币为$a2[i]$，损耗的金币为$m[i-1]$，此时$l[1][i]=l[1][i-1]+a2[i]-m[i-1]$。或者从$l[0][i-1]$向下走一格后向右走一格，此时获得的金币为$a2[i]$，损耗的金币为$m[i-1]$，此时$l[1][i]=l[0][i-1]+a2[i]-m[i-1]$，因此获得转移方程：$l[1][i]=max(l[1][i-1]+a2[i]，l[1][i-1]+a2[i]-m[i-1]，l[0][i-1]+a2[i]-m[i-1])$

  • 始终在第三行：$l[2][i]$位置的金币数可能为$l[2][i-1]$直接向右侧走一列到达即$l[2][i]=l[0][i-1]+a3[i]$，或者从$l[1][i-1]$向下走一格后向右走一格，此时获得的金币为$a3[i]$，损耗的金币为$m[i-1]$，此时$l[2][i]=l[1][i-1]+a3[i]-m[i-1]$。因此获得转移方程：$l[2][i]=max(l[0][i-1]+a3[i]，l[1][i-1]+a3[i]-m[i-1])$

图解


核心代码 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 变相
     * @param n int整型 
     * @param a1 int整型一维数组 
     * @param a2 int整型一维数组 
     * @param a3 int整型一维数组 
     * @param m int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m) {
        // write code here
        int[][] array = new int[3][n];
        array[0][0] = a1[0];//起始位置(1,1),获得金币a1[0]
        array[1][0] = a2[0];//起始位置(2,1),获得金币a2[0]
        array[2][0] = a3[0];//起始位置(3,1),获得金币a3[0]
        for (int i = 1; i < n; i++)
        {//转移方程如下分别表示第1行、第2行、第3行
        array[0][i]=Math.max(array[0][i-1]+a1[i], array[1][i-1]-m[i-1]+a1[i]);//第一行往右一格走
        array[1][i]=Math.max(Math.max(array[1][i-1]+a2[i],array[0][i-1]-m[i-1]+a2[i]), array[2][i-1]-m[i-1]+a2[i]);//第二行往右一格走
        array[2][i]=Math.max(array[2][i-1]+a3[i], array[1][i-1]-m[i-1]+a3[i]);//第三行往右一格走
        }
    return Math.max(array[0][n-1],Math.max(array[1][n-1], array[2][n-1]));
    }
}
复杂度分析
  • 时间复杂度：循环遍历n次找到下一列的最多钱币数，因此时间复杂度为$O(n)$
  • 空间复杂度：借助于一个二维的辅助数组用于存储不同行的每一列位置的最多钱币数，空间复杂度为$O(n)$

方法二

思路分析

     对于方法一我们还可以直接利用给定的数组，直接将不同行的不同列的最多钱币数一直累加到数组中，从而减去辅助数组的开销。

核心代码 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 变相
     * @param n int整型 
     * @param a1 int整型一维数组 
     * @param a2 int整型一维数组 
     * @param a3 int整型一维数组 
     * @param m int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m) {
        // write code here
        for(int i=1;i<n;i++)
        {
            a1[i]+=Math.max(a1[i-1],a2[i-1]-m[i-1]);//第一行往右一格走
            a2[i]+=Math.max(a2[i-1],Math.max(a1[i-1]-m[i-1],a3[i-1]-m[i-1]));//第二行往右一格走
            a3[i]+=Math.max(a3[i-1],a2[i-1]-m[i-1]);//第三行往右一格走
        }
        return Math.max(a1[n-1],Math.max(a2[n-1],a3[n-1]));
    }
}

复杂度分析

  • 时间复杂度：循环遍历n次找到下一列的最多钱币数，因此时间复杂度为$O(n)$
  • 空间复杂度：无需借助辅助数组，因此空间复杂度为$O(1)$