题解 | #礼物的最大价值#

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param grid int整型二维数组 
        * @return int整型
    */
    fun maxValue(grid: Array<IntArray>): Int  {
        val record = Array<IntArray>(grid.size + 1) {
            IntArray(grid[0].size + 1)
        }
        for(i in 1..grid.size) {
            for(j in 1..grid[0].size) {
                //因为只能向下或向右移动，所以当前的最大价值等于上面或者左边的值最大加上当前的值
                record[i][j] = maxOf(record[i - 1][j], record[i][j - 1]) + grid[i - 1][ j - 1]
            }
        }
        return record[grid.size][grid[0].size]
    }
    

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param grid int整型二维数组 
        * @return int整型
    */
    fun maxValue(grid: Array<IntArray>): Int  {
        //注意到其实我们只用到上一个数组的值，即record[i - 1][j]，所以维护两个一维数组即可
        val record = IntArray(grid[0].size + 1)
        val temp = IntArray(grid[0].size + 1)
        for(i in 1..grid.size) {
            for(j in 1..grid[0].size) {
                temp[j] = maxOf(record[j], temp[j - 1]) + grid[i - 1][ j - 1]
            }
            System.arraycopy(temp, 0, record, 0, record.size)
        }
        return record[grid[0].size]
    }
    
}

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param grid int整型二维数组 
        * @return int整型
    */
    fun maxValue(grid: Array<IntArray>): Int  {
        //注意到我们其实只用了上一个数组的相同j的值（即record[i - 1][j]），使用滚动数组还是浪费空间的，我们可以只使用一个一维数组也是可以的
        val record = IntArray(grid[0].size + 1)
        for(i in 1..grid.size) {
            for(j in 1..grid[0].size) {
                //此时等号右边的record[j]相当于record[i - 1][j]，因为此时的record[j]还没有被重新赋值，所以值还是等于record[i - 1][j]，所以我们用一个数组即可
                record[j] = maxOf(record[j], record[j - 1]) + grid[i - 1][ j - 1]
            }
        }
        return record[grid[0].size]
    }
    
}

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param grid int整型二维数组 
        * @return int整型
    */
    fun maxValue(grid: Array<IntArray>): Int  {
        val record = Array<IntArray>(grid.size) {
            IntArray(grid[0].size)
        }
        var max = 0
        for(i in grid.indices) {
            for(j in grid[0].indices) {
                max = maxOf(max, dfs(grid, record, i, j))
            }
        }
        return max
    }
    
    private fun dfs(grid: Array<IntArray>, record: Array<IntArray>, down: Int, right: Int): Int {
        if(down == grid.size || right == grid[0].size) return 0
        //已经计算过直接返回结果
        if(record[down][right] > 0) return record[down][right]
        //一个点只能向下或向右移动所以 一个点的最大值计算过后他就不会再改变，所以我们可以先计算所有还没有计算过的点的最大值
        var sum = grid[down][right]
        sum += maxOf(dfs(grid, record, down + 1, right), dfs(grid, record, down, right + 1))
        record[down][right] = sum
        return sum
    }
}