算法思想

这道题可以类比这背包问题，就可以猜出来要用dp解决

这道dp题属于比较简单，因为题目中就告诉了我们很多信息

集合的属性：Max（一般问题问的什么属性就是什么）

集合的状态：因为是二维数组，比较容易想到是二维状态，表示走到(i,j)这个点的最大价值

集合的划分：一般看的是最后一步的状态，题目已经告诉我们向右走和向下走，所以也就划分为最后一步向左走和向下走到达中终点

有意思的一点是，如果向下面这么写,会出现数组越界的问题，原本想的加一个if判断就可以了，但是这样的话会有一些状态没有达到，所以有了一个完美的解决方案，从1开始循环，grid[i - 1][j - 1]

for(int i = 0; i < n; i ++)
    for(int j = 0; j < m; j ++)
    {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
    }

java代码

class Solution {
    public int getMaxValue(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dp = new int[n + 10][m + 10];

        dp[0][0] = grid[0][0];
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
            }

        return dp[n][m];

    }
}