礼物的最大价值

问题描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

问题分析

很容易可以想到动态规划，假设dp[i][j]表示从左上角到(i,j)位置时礼物的最大值，由于每次只能像右或者像下移动一格，所以dp[i][j]只有由dp[i-1][j]或者dp[i][j-1]这两个位置之一转移过来，为了获得最大的礼物值，将选择总价值较大的上一位置。考虑到边界条件，共有以下三种情况： 1、当i = 0且j != 0时，dp[i][j] = dp[i][j] + dp[i][j-1] 2、当i != 0且j = 0时，dp[i][j] = dp[i][j] + dp[i-1][j] 3、当i != 0且j != 0时，dp[i][j] = dp[i][j] + max(dp[i][j-1], dp[i-1][j])

为了节省空间，我们可以不定义新的数组，直接在原数组上进行操作

代码

class Solution { public int maxValue(int[][] grid) { int res = 0; if(grid.length == 0) return 0; for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[0].length; j++){ if(i == 0 && j != 0) grid[i][j] += grid[i][j-1]; else if(i != 0 && j == 0) grid[i][j] += grid[i-1][j]; else if(i != 0 && j != 0) grid[i][j] += Math.max(grid[i][j-1], grid[i-1][j]); } } return grid[grid.length-1][grid[0].length - 1]; } }

性能分许

依次遍历一遍整个地图，故时间复杂度为O(MN) 在该算法中，没有定义新的变量，故空间复杂度为O(1)