两道相似的三维dp动态规划题

两道相似的三维dp动态规划题

题目描述

洛谷- P1004[NOIP2000 提高组] 方格取数

设有 N×N 的方格图 ( N≤9 )，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:

A
 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                         B
1
2
3
4
5
6
7
8
9
10

某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。 此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。

力扣-741. 摘樱桃

一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：
0 表示这个格子是空的，所以你可以穿过它。 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。 -1 表示这个格子里有荆棘，挡着你的路。 你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：
从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）； 当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子； 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）； 如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。

---

思路

两道题都是从左上角到右下角走两次，每一步只能朝右或朝下走一格，途中捡起对应的奖励，求奖励和的最大值。不一样的是第二道题还有障碍物，有可能没有满足条件的解。

这道题当然可以考虑递归搜索算法，但是可能会超时。所以推荐动态规划去处理。
那么问题来了，要怎么定义状态呢？最暴力的就是dp[x1][y1][x2][y2]代表第一个角色在grid[x1][y1]的同时第二个角色在grid[x2][y2]时的最大奖励数，答案也就是dp[n][m][n][m]。那么就是4维DP了，可是这里有个关系，就是时间一致性。x1+y1 == x2+y2必须满足，否则不是同一时间的。那么就设x1+y1 = x2+y2 = k. DP的状态压缩一下：dp[k][i][j]代表走完第k步后，角色1在grid[i][k-i]，角色2在grid[j][k-j]情况下最大奖励值。
定义完状态后，其实我们就可以状态转移求解最优化值了。这种也只有4种情况，都从左边、一左一上、一上一左、都从上边。
具体代码Go语言
AC代码

package main
​
import (
    "fmt"
)
​
func main() {
    var n, x, y, v int
    var grid [15][15]int
    var dp [25][15][15]int
    max := func(arr ...int) int {
        res := 0
        for _, v := range arr {
            if res < v {
                res = v
            }
        }
        return res
    }
    fmt.Scan(&n)
    for {
        fmt.Scan(&x, &y, &v)
        if x == 0 && y == 0 && v == 0 {
            break
        }
        grid[x][y] = v
    }
    dp[0][0][0] = grid[1][1]
    for k := 1; k < 2*n-1; k++ {
        for i := 0; i <= k; i++ {
            for j := i; j <= k; j++ {
                if i >= n || j >= n || k-i >= n || k-j >= n {
                    continue
                }
                s := 0
                s += grid[1+i][1+k-i]
                if i != j {
                    s += grid[1+j][1+k-j]
                }
                if i > 0 {
                    dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-1][j], dp[k-1][i][j-1], dp[k-1][i-1][j-1]) + s
                } else if j > 0 {
                    dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i][j-1]) + s
                } else {
                    dp[k][i][j] = dp[k-1][i][j] + s
                }
            }
        }
    }
    fmt.Println(dp[2*n-2][n-1][n-1])
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

AC代码

func cherryPickup(grid [][]int) int {
    n := len(grid)
    dp := make([][][]int,2*n-1)
    max := func(a,b int) int {if a > b {return a}; return b}
    for i := 0; i < 2*n-1; i++ {
        dp[i] = make([][]int,n)
        for j := 0; j < n; j++ {
            dp[i][j] = make([]int,n)
            for k := 0; k < n; k++ {dp[i][j][k] = -0x3f3f3f3f}
        }
    }
    dp[0][0][0] = grid[0][0]
    for k := 1; k < 2*n-1; k++ {
        for i := 0; i <= k && i < n; i++ {
            x1,y1 := i,k-i
            if y1 >= n || grid[x1][y1] == -1  {continue}
            for j := i; j <= k && j < n; j++ {
                x2,y2 := j,k-j
                res := -0x3f3f3f3f
                if y2 >= n || grid[x2][y2] == -1 {continue}
                if x1-1 >= 0 && x2-1 >= 0 {res = max(res,dp[k-1][x1-1][x2-1])}
                if x1-1 >= 0 {res = max(res,dp[k-1][x1-1][x2])}
                if x2-1 >= 0 {res = max(res,dp[k-1][x1][x2-1])}
                res = max(res,dp[k-1][x1][x2])
                if x1 == x2 {
                    dp[k][x1][x2] = res + grid[x1][y1]
                } else {
                    dp[k][x1][x2] = res + grid[x1][y1] + grid[x2][y2]
                }
            } 
        }
    }
    if dp[2*n-2][n-1][n-1] < 0 {return 0}
    return dp[2*n-2][n-1][n-1]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35