785. 最大权值和路径

描述

有一个机器人位于一个 m × n 个网格的右上角。
机器人每一时刻只能向下或者向左移动一步。机器人试图达到网格的左下角。每个网格上有一个数字权值，机器人希望它走到左下角的路径权值和最大。
问这个最大路径权值和是多少？

注意事项

输入一个n x m 的矩阵，保证 n <= 200,m <= 200。
题目数据保证 0 <= i <= n-1 , 0 <= j <= m-1, nums[i][j] <= 100000。
您在真实的面试中是否遇到过这个题？ Yes
样例
给出
[
[1,2,3,4],
[3,5,6,7],
[9,10,1,2],
[4,4,5,5]
]，返回45。
解释：

从右上角出发，沿着[4,7,6,5,10,9,4]走到左下角。权值和为45。
给出
[
[1,2,3],
[4,5,6],
[7,9,8]
]
,返回33。
解释：
从右上角出发，沿着[3,6,8,9,7]走到左下角，权值和为33。

思路
等同于 114. 不同的路径 这题

代码

public class Solution {
    /**
     * @param nums: the n x m grid
     * @return: the maximum weighted sum
     */
    public int maxWeight(int[][] nums) {
        if (nums == null || nums.length == 0 || nums[0].length == 0) {
            return 0;
        }
        
        int m = nums.length;
        int n = nums[0].length;
        int[][] sum = new int[m][n];
        
        sum[0][n - 1] = nums[0][n - 1];
        for (int i = 1; i < m; i++) {
            sum[i][n - 1] = nums[i][n - 1] + sum[i - 1][n - 1];
        }
        for (int i = n - 2; i >= 0; i--) {
            sum[0][i] = nums[0][i] + sum[0][i + 1];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = n - 2; j >= 0; j--) {
                sum[i][j] = Math.max(sum[i - 1][j], sum[i][j + 1]) + nums[i][j];
            }
        }
        
        return sum[m - 1][0];
    }
}