Sword47——礼物的最大价值

方法1——动态规划

思路：每个单元格只能从左边或上面移动到此处，因此从左上角遍历，将每个单元格可取得的最大礼物价值直接存入矩阵即可 特殊情况与临界分析：见于步骤中 终止条件：到达矩阵右下角 步骤： 获取矩阵的行列数 双重for循环遍历矩阵 特殊情况： 当i、j均为0时，证明为第一格，直接continue跳过 当i为0时证明为第一行，只能从左侧移动 当j为0时证明为第一列，只能从上面移动 当以上特殊情况都不满足，比较左侧和上面两个单元格，选择较大值加上自身值存入单元格中 返回最右下角的最大值

public int maxValue(int[][] grid) {
          
   
        // 获取矩阵的行列数
        int rows = grid.length, columns = grid[0].length;
        // 双重for循环遍历矩阵
        for (int i = 0; i < rows; i++) {
          
   
            for (int j = 0; j < columns; j++) {
          
   
                // 当i、j均为0时
                if (i == 0 && j == 0) {
          
   
                    continue;
                }
                // 当i为0时，证明为第一行
                if (i == 0) {
          
   
                    grid[i][j] += grid[i][j - 1];
                // 当j为0时，证明为第一列
                } else if (j == 0) {
          
   
                    grid[i][j] += grid[i - 1][j];
                // i、j均不为0时，选择左侧或上面的较大值
                } else {
          
   
                    grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
                }
            }
        }
        // 返回右下角的值
        return grid[rows - 1][columns - 1];
    }