动态规划

C++ 代码

class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        dp[0][0] = grid[0][0];
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < m; ++ j)
            { 
                if(i) dp[i][j] = max(dp[i][j], dp[i - 1][j] + grid[i][j]);
                if(j) dp[i][j] = max(dp[i][j], dp[i][j - 1] + grid[i][j]);
            }
        return dp[n - 1][m - 1];
    }
};