public class SO47_MaxValue {
    public static void main(String[] args) {

    }

    public int maxValue(int[][] grid){
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n]; // m,n 时的最大值
        dp[0][0] = grid[0][0];
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (i == 0 && j==0) continue;
                if (i ==0) {
                    dp[i][j] += dp[i][j-1]+grid[i][j];
                } else if (j ==0) {
                    dp[i][j] += dp[i-1][j] + grid[i][j];
                } else {
                    dp[i][j] += Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];
    }

    public int maxValue2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (i==0 && j==0) continue;
                if (i==0) {
                    grid[i][j] += grid[i][j-1];
                } else if(j ==0) {
                    grid[i][j] += grid[i-1][j];
                } else {
                    grid[i][j]+= Math.max(grid[i-1][i], grid[i][j-1]);
                }
            }
        }
        return grid[m-1][n-1];
    }
}
// 多开一行一列的空间能够让代码更简洁
class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
        int[][] dp = new int[row + 1][column + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= column; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[row][column];
    }
}