【剑指Offer】47. 礼物的最大价值

class Solution {
    public int maxValue(int[][] f) {
        // 经典二维动态规划 f[i][j] = max(f[i-1][j], f[i][j-1])
        int r = f.length;
        int c = f[0].length;
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(i == 0 && j == 0) continue;
                if(i == 0) f[i][j] += f[i][j-1];
                else if(j == 0) f[i][j] += f[i-1][j];
                else f[i][j] += Math.max(f[i-1][j], f[i][j-1]);
            }
        }
        return f[r-1][c-1];
    }
}

1    10   3    8
12   2    9    6
5    7    4    11
3    7    16   5

public int getMost(int[][] values) {
    if (values == null || values.length == 0 || values[0].length == 0)
        return 0;
    int n = values[0].length;
    int[] dp = new int[n];
    for (int[] value : values) {
        dp[0] += value[0];
        for (int i = 1; i < n; i++)
            dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];
    }
    return dp[n - 1];
}