在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0).你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格,直到到达棋盘的右下角.给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
假设二维数组dp[i][j]表示单元格 (i j)(ij) 的礼物最大累计价值,由于题目说到每次向右或者向下移动一格,所以可以到达整个单元格的方式,只能从上(i,j-1)和左边(i-1,j)的单元格达到,并且取这两个单元格的最大值,并可以推导出公式
在具体写法需要考虑,到第一行和第一列的边界问题,因为第一行只能从左边到达,第一列只能从上到达,所以,可以将二维数组的大小初始化的+1,遍历时i,j从1开始,避免从grid(ij)取值的时,出现越界问题.