动态规划

①确定状态：设走到格子 grid[x,y] 时，能获得的最大价值为 f(x,y)。

分析最后一步，即走到了右下角 grid[m,n]，根据题意，其上一步只能是 grid[m-1,n] 或 grid[m,n-1]，那么为了获得最大价值的礼物，此时就会选择能够获得价值较大的那一项作为上一步，假如 f(m-1,n) > f(m,n-1)，那么 grid[m,n] 的上一步就应该是 grid[m-1,n]，所以当走到格子 grid[m,n] 时能获得的最大价值为上一步所获得的最大价值加上当前格子获得的价值，即 f(m,n) = f(m-1,n) + grid[m,n] 。

子问题：走到格子 grid[m-1,n] 时，其上一步只有 grid[m-2,n] 或 grid[m-1,n-1] 两种可能，那么 f(m-1,n) 的值就会根据 f(m-2,n) 和 f(m-1,n-1) 的较大值而定。

②状态转移方程：f(x,y) = max{ f(x-1,y), f(x,y-1) } + grid[x,y]

③初始条件：f(0,0)=grid[0,0]

④边界情况：位于二维数组 grid 顶边缘和左边缘的格子，其上一步只有一种可能，比如 grid[0,2]，其上一步只能是 grid[0,1]。

时间复杂度：O(NM) ，需要遍历二维数组

空间复杂度：O(NM) ，需要维护一个二维的状态数组

class Solution {
    public int maxValue (List<List<int>> grid) {
        int[,] maxValue=new int[grid.Count,grid[0].Count]; //状态数组
        int max=int.MinValue; //记录历史最大值
        //遍历二维数组：
        for(int i=0;i<grid.Count;++i){
            for(int j=0;j<grid[0].Count;++j){
                if(i==0 && j==0){ //起点格子
                    maxValue[i,j]=grid[i][j];
                }else if(i==0 && j!=0){ //顶边缘的格子
                    maxValue[i,j]=maxValue[i,j-1]+grid[i][j];
                }else if(i!=0 && j==0){ //左边缘的格子
                    maxValue[i,j]=maxValue[i-1,j]+grid[i][j];
                }else{
                    maxValue[i,j]=Math.Max(maxValue[i-1,j], maxValue[i,j-1])+grid[i][j];
                }
                //维护历史最大值：
                if(maxValue[i,j]>max){
                    max=maxValue[i,j];
                }
            }
        }
        return max;
    }
}

优化空间复杂度

基于上面的算法，我们可以进一步将空间复杂度优化为O(N)。

以下我们将到达某个格子时所能获得的最大价值称为 maxValue。

已知要计算 grid[x,y] 的 maxValue 只依赖于 grid[x-1,y] 和 grid[x,y-1] 的 maxValue；

要计算 grid[x,y+1] 的 maxValue 只依赖于 grid[x-1,y+1] 和 grid[x,y] 的 maxValue；

也就是说：当我们在枚举二维数组 grid 的第 x 行时，我们只需要知道上一行也就是第 x-1 行的 maxValue 和当前格子左边所有格子的maxValue。

那么我们就只需要维护一个一维的状态数组来记录 maxValue 即可，只记录我们用得上的 maxValue，状态数组的长度为数组 grid 的列数。

举个栗子，假设现在存在一个 3×5 的二维数组 grid，下标索引从0开始。当前枚举到了 grid[1,2]，那么此时状态数组的前2位就记录 grid[1,2] 左边所有格子的maxValue；而状态数组的后3位则记录当前格子的上一行从第2位到第4位的所有格子的 maxValue。接着下一轮循环枚举到 grid[1,3]，那么状态数组的第2位就更新为 grid[1,2] 的 maxValue，以此类推。

下图展示了在一个 3×5 的二维数组 grid 中，从 grid[1,2] 枚举到 grid[2,2] 时，状态数组的变化过程。红色部分代表当前枚举到的格子，绿色部分代表状态数组需要记录的格子。

alt

class Solution {
    public int maxValue (List<List<int>> grid) {
        int[] maxValue=new int[grid[0].Count]; //状态数组
        int max=int.MinValue; //记录历史最大值
        //遍历二维数组：
        for(int i=0;i<grid.Count;++i){
            for(int j=0;j<grid[0].Count;++j){
                if(i==0 && j==0){ //起点
                    maxValue[j]=grid[i][j];
                }else if(i==0 && j!=0){ //顶边缘的格子
                    maxValue[j]=maxValue[j-1]+grid[i][j];
                }else if(i!=0 && j==0){ //左边缘的格子
                    maxValue[j]=maxValue[j]+grid[i][j];
                }else{
                    maxValue[j]=Math.Max(maxValue[j], maxValue[j-1])+grid[i][j];
                }
                //维护历史最大值：
                if(maxValue[j]>max){
                    max=maxValue[j];
                }
            }
        }
        return max;
    }
}

题解 | #礼物的最大价值# 动态规划（图解）

动态规划

优化空间复杂度