算法1

$O(n*m)$

当前位置的的价值和它左边还有上面的的礼物价值有关

根据上面的规律，清除整个矩阵所有位置的最大价值，就可以等到右下角位置的最大价值了

注意：从左上角比较右边和下边的大小，迭代是不可行的，因为如果出现一样的，并不知道这两个的路径，后面的价值哪一个大。

Java 代码

class Solution {
    public int getMaxValue(int[][] arr) {
 if (arr == null || arr.length == 0) { 
     return 0;
     }
     int rows = arr.length; 
     int cols = arr[0].length; 
     int[][] maxValue = new int[rows][cols];
     for (int i = 0; i < rows; i++) {
         for (int j = 0; j < cols; j++) {
             int left = 0; 
             int up = 0; 
             if(i>0){
                 up = maxValue[i-1][j];
             } 
             if(j>0){
                 left = maxValue[i][j-1]; 

             } 
                 maxValue[i][j] = Math.max(up, left) + arr[i][j]; 

         } 

     }
     return maxValue[rows-1][cols-1];
    }
}

算法2

$O(n*m)$

用一个一维数组降低空间复杂度

Java 代码

class Solution {
    public int getMaxValue(int[][] m) {
        if(m==null||m.length==0||m[0]==null||m[0].length==0)
            return 0;

        int more = Math.max(m.length,m[0].length);
        int less = Math.min(m.length,m[0].length);

        boolean rowmore = more == m.length;
        int arr[] = new int[less];
        arr[0] = m[0][0];
        for(int i = 1;i<less;i++){
            arr[i] = arr[i-1]+(rowmore?m[0][i]:m[i][0]);
        }
        for(int i = 1;i<more;i++){
            arr[0] = arr[0]+(rowmore?m[i][0]:m[0][i]);
            for(int j =1 ; j<less;j++){
                arr[j] = Math.max(arr[j-1],arr[j])+(rowmore?m[i][j]:m[j][i]);
            }
        }
        return arr[less-1];
    }
}