(C++/Python)LeetCode剣指Offer 47プレゼントの最大価値

タイトルの説明:1つのm*nの碁盤の各格に1つの贈り物が置いて、すべての贈り物はすべて一定の価値があります(価値は0より大きい).碁盤の左上から格子の中の贈り物を取り始め、碁盤の右下に着くまで右または下に1格ずつ移動することができます.碁盤とその上の贈り物の価値を与えて、あなたが最大でどれだけの価値の贈り物を得ることができるかを計算してください.
例1:
入力:[[1,3,1],[1,5,1],[4,2,1]]出力:12解釈:経路1→3→5→2→1が最も価値のある贈り物を受け取ることができる
構想:動的計画は1つの位置に達するたびに、その上と左の最大値を比較し、(左からか右からか)現在の位置の値を加算します.
コードは次のとおりです:2 D:

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

1次元に変更:

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        vector<int>dp(grid[0].size()+1);
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                dp[j+1]=max(dp[j],dp[j+1])+grid[i][j];
            }
        }
        return dp.back();
    }
};

Python:

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid: return 
        dp=[0 for _ in range(len(grid[0])+1)]
        # dp=[0]*(len(grid[0])+1)
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                dp[j+1]=max(dp[j],dp[j+1])+grid[i][j]
        return dp[-1]