LintCode：785. 最大权值和路径（动态规划）

思路：这是一道典型的动态规划题，思路类似于背包问题，dp中每个元素的值分别是来自于该位置上方和该位置右边的较大的一个值，新建dp矩阵，int[][] dp=new int[row+1][col+1]。

注意是从右上角开始到左下角结束，状态转移方程为 dp[i][j]=max(dp[i][j+1]+nums[i-1][j],dp[i-1][j]+nums[i-1][j])（i从1开始，j从col-1递减，所以dp[i][j]对应的权值矩阵为nums[i-1][j])

最后返回的是左下角元素dp[row][0].

public class Solution {
    /**
     * @param nums: 
     * @param k: 
     * @return: nothing
     */
    public int maxWeight(int[][] nums) {
        int row=nums.length;
        int col=nums[0].length;
        int[][] dp=new int[row+1][col+1];
        for(int i=1;i<=row;i++){
            for(int j=col-1;j>=0;j--){
                dp[i][j]=Math.max(dp[i][j+1]+nums[i-1][j],dp[i-1][j]+nums[i-1][j]);  //分别从右边和从上边的
            }
        }
        return dp[row][0];
    }
}