题目描述

在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

样例

输入：
[
  [2,3,1],
  [1,7,1],
  [4,6,1]
]

输出：19

算法

(线性DP)

f[i][j]代表从左上角走到(i, j)这个位置时的最大价值。
题目规定只能向下or向右走，所以(i, j)这个位置的状态只能从左边or上边转移过来。
所以$f[i][j] = max(f[i - 1][j], f[i][j - 1]) + A[i][j]$。

时间复杂度

$O(n^2)$

C++ 代码

class Solution {
public:
    int getMaxValue(vector<vector<int>>& A) {
        int n = A.size(), m = A[0].size();
        vector<vector<int> > f(n + 1, vector<int> (m + 1, 0));
        f[0][0] = 0;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + A[i - 1][j - 1];

        return f[n][m];
    }
};