跟着姚桑学算法-礼物的最大价值

题. 礼物的最大价值

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

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

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

注意：

• m,n>0
• m×n≤1350

样例：

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

输出：19

解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

【题解】--- 动态规划

基本思想

动态规划算法 通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

__这就是动态规划法的基本思路__。具体的动态规划算法多种多样，但它们具有相同的填表格式。

本题是经典的DP问题，dp[i][j] 代表走到（i，j）这个位置的最大价值;

由于只能向下向右走，所以（i，j）这个位置只能从左边和上边过来，

所以dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j],即从左边和上边这两个位置选一个较大的加上本位置的价值即可得出解。

复杂度分析：

本题要对每一个状态进行状态转移，时间复杂度为O(n^2)。

C++代码实现：

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

        for (int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]?dp[i-1][j]:dp[i][j-1]) + grid[i][j];

            }
        }
        // cout<<dp[1][0]<<dp[2][0];
        return dp[m-1][n-1];
    }
};