LeetCode—剑指 Offer 47. 礼物的最大价值

题目来源于 LeetCode 的剑指 Offer 47题，难度为：中等。目前的通过率是68.8%。

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

??首先像这种求最值的问题，一般都是往 动态规划 上面去靠。但是即使知道使用动态规划，但是定义dp的状态表达的意义也是一件不容易的事情，不过我们可以多看多做几种类型的题，为自己的知识库积累下解题的思路。以后遇见类似的题的时候，可以直接套。一句话就是：都是套路。
??那么今天我直接使用动态规划进行解题了。
??为了更好的演示效果，我们选取一个 4*4 的测试用例，
输入：

1grid = [
2??   [1,3,1,2], 
3         [1,5,1,3], 
4         [4,2,1,4],
5         [3,2,6,5]
6?]

解题思路：

定义dp的意义：dp[row][col] 是走到 [row][col] 位置时的最大值。
如下图：

思考：那么你是如何走到 [row][col] 位置的？只有有2种可能

1、从[row][col-1]位置往右走
2、从[row-1][col]位置往下走

比如走到 [1][1] 这个位置时的值，只有2种走法：

1、紫色线的走法: 1->1->5 = 7
2、红色线的走法: 1->3->5 = 9
那么走到[row][col]位置时的最大值就是9,对应红框标记的值。

??接下来我们就可以定义状态转移方程了，也就是确定 dp[row][col] 与【dp[row][col]、dp[row][col]】之间的关系了，通过上述讲解，我们可以很清楚的确定状态转移方程：

1  dp[row][col] = grid[row][col] + max{dp[row][col],dp[row][col]}

??下面我们将一些特殊情况处理下，因为每一步只能往右走或者往下走，所以图中的黑色部分是特殊情况。比如像到达 [0][3] 的位置就只能每一步都往右走，所以 dp[0][3] = 1+3+1+2 = 7,图中的黑色部分就可以很快的确定下来。
??接下来就是求橙色部分的了，可以一行一行的求，使用状态转移方程即可。

代码：

 1class Solution {
 2     func maxValue(_ grid: [[Int]]) -> Int {
 3        if grid.count == 0 || grid[0].count == 0 { return 0 }
 4        let rows = grid.count
 5        let cols = grid[0].count
 6        var dp = [[Int]](repeating: [Int](repeating: 0, count: cols), count: rows)
 7        dp[0][0] = grid[0][0]
 8        // 第0行
 9        for i in 1..<cols {
10            dp[0][i] = grid[0][i] + dp[0][i-1]
11        }
12        // 第0列
13        for i in 1..<rows {
14            dp[i][0] = grid[i][0] + dp[i-1][0]
15        }
16
17        for (i, nums) in grid.enumerated() {
18            if i == 0 { continue }
19            // 一行一行的求 dp[i][j]
20            for (j, _) in nums.enumerated() {
21                if j == 0 { continue }
22                dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
23            }
24        }
25        return dp[rows - 1][cols - 1]
26    }       
27} 
28

结尾

??动态规划的题目其实都是很有意思的，多看多做几道这样的题目就可以很快的掌握动态规划这种求最值的解题思路了。