72、礼物的最⼤价值

题⽬描述

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

如输⼊这样的⼀个⼆维数组，

那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为 12

这道题其实⼀看就知道是动态规划，棋盘中的每个⼩格⼦，都是和上⽅，或者左⽅的格⼦有关。既然是动态规划，那么我们先定义状态：

dp[i][j]表示到达(i,j)位置时能获得的最大礼物价值

状态转移：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j] 每个位置的计算只依赖左边和上边的结果，通过双重循环自左上向右下填充整个dp表

观察发现当前行只依赖上一行，可以使用一维数组进行空间优化，利用dp[j]在更新前存储上一行第j列的值，更新后存储当前行第j列的值，实现空间复用

dp[j]表示当前行第j列的最大价值，滚动更新

修改原数组，直接使用grid数组作为dp表，避免额外空间分配