代码

简单的二维DP，比较下多开一行一列数组从而不考虑边界的优势：

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        /* f开(m+1)*(n+1)，不需考虑边界 */
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> f(m+1, vector<int>(n+1));
        for(int i = 1; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                f[i][j] = max(f[i-1][j], f[i][j-1]) + grid[i-1][j-1];
            }
        }
        return f[m][n];

        /* f只开m*n, 需要考虑边界 */
        // int m = grid.size(), n = grid[0].size();
        // vector<vector<int>> f(m, vector<int>(n));
        // f[0][0] = grid[0][0];
        // int dx[2] = {0, 1}, dy[2] = {1, 0};
        // for(int i = 0; i < m; i ++){
        //     for(int j = 0; j < n; j ++){
        //         for(int k = 0; k < 2; k ++){
        //             int x = i - dx[k], y = j - dy[k];
        //             if(x >= 0 && x < m && y >= 0 && y < n)
        //                 f[i][j] = max(f[i][j], f[x][y] + grid[i][j]);
        //         }
        //     }
        // }

        // return f[m-1][n-1];
    }
};