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

礼物的最大价值

https://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134

kotlin
动态规划基础版
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
    }
}



全部评论

相关推荐

码农索隆:想看offer细节
点赞 评论 收藏
分享
每晚夜里独自颤抖:这个在牛客不是老熟人了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务