劍指offer 47.禮物的最大價值

題目位址

解題思路

首先我們思考：當我們處于矩陣中某個正常單元格時，此時該單元格的最大價值profit[i][j]應該怎麼計算呢？

我們可以很容易得出：

profit[i][j]=max(profit[i-1][j],profit[i][j-1]) + grid[i][j];

即處于目前單元格時的最大價值等于（上面一格和左邊一個 中 最大價值的較大值） 加 目前單元格的價值；

當然會有一些特殊情況，比如第一行的單元格，第一列的單元格，這些情況需要單獨處理：

具體處理細節在下面的代碼中都有展現：

代碼實作（C++）

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) 
    {
        if(grid.size()==0 || grid[0].size()==0)
        {
            return 0;
        }
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> profit(m,vector<int>(n,0));

        for(int i=0;i!=m;i++)
        {
            for(int j=0;j!=n;j++)
            {
                if(i==0&&j==0)
                {
                    profit[i][j]=grid[i][j];
                }
                else if(i==0)
                {
                    profit[i][j]=profit[i][j-1]+grid[i][j];
                }
                else if(j==0)
                {
                    profit[i][j]=profit[i-1][j]+grid[i][j];
                }
                else 
                {
                    profit[i][j]=max(profit[i-1][j],profit[i][j-1])+grid[i][j];
                }
            }
        }
        return profit[m-1][n-1];
    }
};