算法动态规划

多进程DP：一个阶段控制两个独立的附加信息

字数统计: 1.6k字   |   阅读时长: 6分
,

摘要: 多进程 DP

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

当明确了动态规划的阶段要素后，经常会发现发现阶段不足以表示状态，需要增加额外信息作为状态的维度，例如 阶段不足表示状态：附加信息作为状态维度。

有的时候会出现多个额外信息分别隶属于不同的对象的情况。阶段每推导一步，不同的对象各自独立地改变自己的附加信息，此时状态推导过程有点类似于多进程。称其为多进程 DP。其状态定义一般有以下形式：

其中 $i$ 是阶段，$x$ 是对象 1 的信息，$y$ 是对象 2 的信息。当阶段推导 1 步，对象1和对象2独立地行动，分别将附加信息改变为 $x’$、$y’$，形成新的状态 $dp[i+1][x’][y’]$。

下面三道题都是这种情况：

题目 状态表示
741. 摘樱桃 $dp[i][x_{1}][x_{2}]$，$i$ 为已走过的步数，$x_1,x_2$ 为两个人的横坐标
1463. 摘樱桃 II $dp[i][j_{1}][j_{2}]$，$i$ 为已走过的步数，$j_1,j_2$ 为两个人的横坐标
1320. 二指输入的的最小距离 $dp[i][x][y]$，$i$ 为已取出的字母个数，$x, y$ 为两个手指的位置

本文通过第 1 个题来看一下多进程 DP 的特点以及实现思路。

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) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。

说明:

1
2
3
4
5
6
n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] 为 -1、0 或 1
grid[0][0] != -1
grid[n - 1][n - 1] != -1

示例 1:
输入: grid =
[[0, 1, -1],
[1, 0, -1],
[1, 1, 1]]
输出: 5
解释：
玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。

示例 2：
输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0

错误算法: 贪心

先去程走最长，然后更新 grid，然后回程再走最长。

这个算法很直观，也符合直觉，但是是错的，反例如下

贪心给出的去程路线如图中标出，共13个，回程还能取到1个，一共可取到14个。而实际上应该是可以取到15个。

算法: 多进程DP

去程在回程可以理解为从左上找两条路到右下，可以取到的最大值。

这样的话状态由两条线上的位置决定。设 $i$ 步之后的可能位置为 (x, y)，($x+y=i$)。两个人的位置分别为 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$。

状态定义为 $dp[i][x_{1}][x_{2}]$，表示已经走过 $i$ 步，两个人的位置分别为 $x_{1}, x_{2}$ 时，可以取到的最多樱桃。

这样定义的话，目标为 $dp[2N-2][N-1][N-1]$，初始值为 $dp[0][0][0] = grid[0][0]$。

下面考虑状态转移方程，从先前阶段的已知状态计算当前状态。当前阶段两个人的位置为 $x_{1}, x_{2}$，第一个人有可能从左边($x_{1}$)过来，也可能从上边($x_{1}-1$)过来；第二个人也有可能从左边($x_{2}$)过来，也可能从上边($x_{2}-1$)过来。

1
2
3
4
5
6
dp[i][x1][x2] = grid[x1][i-x1] + grid[x2][i-x2]
                + max(dp[i - 1][x1][x2]
                     ,dp[i - 1][x1-1][x2]
                     ,dp[i - 1][x1][x2-1]
                     ,dp[i - 1][x1-1][x2-1]
                     )

上述方程中，还需要注意 x1 = x2 时 grid 只记一次，以及 x1 < 0, x2 < 0, y1 < 0, y2 < 0 导致 grid[x][i-x] = -1 的不合法情况。

代码 (C++)

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
class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<vector<int>>> dp(n + m - 1, vector<vector<int>>(n, vector<int>(n, -1)));
        dp[0][0][0] = grid[0][0];
        for(int i = 1; i < n + m + 1; ++i)
        {
            for(int x1 = max(0, i - m + 1); x1 <= min(n - 1, i); ++x1)
            {
                int y1 = i - x1;
                if(grid[x1][y1] == -1)
                    continue;
                for(int x2 = max(0, i - m + 1); x2 <= min(n - 1, i); ++x2)
                {
                    int y2 = i - x2;
                    if(grid[x2][y2] == -1)
                        continue;
                    // 计算 dp[i][x1][x2]
                    if(x1 < i && x2 < i)
                        dp[i][x1][x2] = max(dp[i][x1][x2], dp[i - 1][x1][x2]);
                    if(x1 < i && x2 > 0)
                        dp[i][x1][x2] = max(dp[i][x1][x2], dp[i - 1][x1][x2 - 1]);
                    if(x1 > 0 & x2 < i)
                        dp[i][x1][x2] = max(dp[i][x1][x2], dp[i - 1][x1 - 1][x2]);
                    if(x1 > 0 && x2 > 0)
                        dp[i][x1][x2] = max(dp[i][x1][x2], dp[i - 1][x1 - 1][x2 - 1]);
                    if(dp[i][x1][x2] != -1)
                    {
                        dp[i][x1][x2] += grid[x1][i - x1];
                        if(x1 != x2)
                            dp[i][x1][x2] += grid[x2][i - x2];
                    }
                }
            }
        }
        if(dp[n + m - 2][n - 1][n - 1] == -1)
            return 0;
        return dp[n + m - 2][n - 1][n - 1];
    }
};
Share