1.题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入:
[ [1,3,1],
[1,5,1],
[4,2,1] ]
输出: 12
解释: 路径 1→3→5→2→1可以拿到最多价值的礼物

提示：

0 < grid.length <= 200
0 < grid[0].length <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.动态规划的解题步骤

这是一个二维动态数组的入门题，不管是几维，解题的步骤是一样的，目前没有做过很多二维题目，这是第一个，但我觉得动态数组是几维数，应该与问题规模有关，比如背包问题，有背包容量和物品体积重量，是个二维的（这是算法设计课程的实验题目，之前不会，还没有去试，但是现在有思路了）。

2.1.dp[i][j]的定义

对上题而言，我们举一个数字，如8,8，那么dp[8][8]就表示之前路径加(8,8)这里的礼物的价值和的最大值。
dp[i][j]就表示选择(i,j)位置时礼物价值的最大值。

2.2.递推式

因为我们只能往下和往右走，那么对于dp[i][j]，就可以得出：
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
对于这个题：
因为我们只能往下和右，所以
当i == 0时我们只能从左边过来，
因此：dp[0][j] = dp[0][j-1] + grid[0][j]

当j == 0时我们只能从上边过来，
因此：dp[i]0] = dp[i][0] + grid[i - 1]0]

2.3.dp初始化和递归函数出口

dp[0][0] = grid[0][0]；//出口

2.4.递归函数

非常的简洁漂亮。

int dp(vector<vector<int>> grid, int i, int j) {
    
    if(i == 0 && j == 0) {
    
        return grid[0][0];
    }
    else if(j == 0) {
    
        return opt_recursion(grid,i - 1,0) + grid[i][0];
    }
    else if(i == 0) {
    
        return opt_recursion(grid,0,j - 1) + grid[0][j];
    }

    return max(dp(grid,i - 1,j), dp(grid,i,j - 1)) + grid[i][j];
}

虽然超时了，但说明我们的思路是对的，并没有错。

2.5.递归改成迭代

因为i = 0或者j = 0时是特殊情况，所以先初始化

int dp_iterate(vector<vector<int>> grid) {
    
    int m = grid.size();
    int n = grid[0].size();

    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    for(int j = 1;j < n;j++) {
    
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    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] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    return dp[m - 1][n - 1];
}

2.6.迭代优化

这是题解中大佬的优化。。

int opt_iterate_better(vector<vector<int>> grid) {
    
    int m = grid.size();
    int n = grid[0].size();

    for(int i = 1;i < m;i++) {
    
        grid[i][0] += grid[i - 1][0];
    }

    for(int j = 1;j < n;j++) {
    
        grid[0][j] += grid[0][j - 1];
    }

    for(int i = 1;i < m;i++) {
    
        for(int j = 1;j < n;j++) {
    
            if(grid[i - 1][j] > grid[i][j - 1]) {
    
                grid[i][j] += grid[i - 1][j];
            }
            else {
    
                grid[i][j] += grid[i][j - 1];
            }
        }
    }

    return grid[m - 1][n - 1];
}

3.结语

做多了就有收获了，知道怎么做了。