算法动态规划

调整状态定义的方向：简化实现过程

字数统计: 1.8k字   |   阅读时长: 7分
,

摘要: 状态定义的方向的影响

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

在文章 状态计算的方向：从已知状态计算当前状态；从当前状态更新后续状态 中，我们知道当阶段划分与状态定义完成后，还可以转换状态定义的方向，以及采用不同的状态计算方向。

  • 状态定义的方向决定了哪边是边界值，哪边是目标。而阶段推导始终是从边界值推导到目标值，
  • 状态计算的方向决定了是从先前阶段的已知状态计算当前状态或，还是从当前状态更新后续阶段的未知状态。

在那篇文章中我们详细讨论了状态计算的两种方向对于算法的推导以及实现的影响。

本文我们看一下状态定义方向对算法推导和实现的影响。

本文通过一个题来看，当状态定义后，发现初始值只有一个，而目标有零零散散的很多时可以做以下处理：

可以尝试改变状态定义方向，使得初始值变成零零散散的多个，而目标值只有一个。此时如果用记忆化搜索，就是目标值出发。由于目标只有一个，在实现的时候需要考虑的问题就少一些，可以起到简化实现的作用。

1463. 摘樱桃 II

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

  • 从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
  • 当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
  • 当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
  • 两个机器人在任意时刻都不能移动到 grid 外面。
  • 两个机器人最后都要到达 grid 最底下一行。

提示：

1
2
3
4
rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

示例 1：
输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出：24
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为： 12 + 12 = 24 。

示例 2：
输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出：28
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为： 17 + 11 = 28 。

示例 3：
输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出：22

示例 4：
输入：grid = [[1,1],[1,1]]
输出：4

算法：多进程DP

阶段划分与附加信息

机器人每一步必须向下走一行，左右的方向可以选择向左走一步，向右走一步，或者维持在原来的列。

因此以行号 $i$ 为阶段，$i$ 也代表已经走过的步数。两个机器人的列号 $j_{1}, j_{2}$ 为附加信息，分别属于两个独立的机器人。

状态定义

因此状态定义为 $dp[i][j_{1}][j_{2}]$ 表示已经走过 $i$ 步，两个机器人的列号分别为 $j_[1], j_{2}$ 时，最多摘取的樱桃数。

这样定义的话，目标是 $\sum\limits_{j=0}\limits^{m-1}dp[n-1][j]$，边界值为 $dp[0][0][m-1]$。阶段按照 $i$ 从小到大推导到 $n-1$。

反向定义状态

注意到这种定一下目标有很多，而边界值只有一个，因此我们换一下定义的方向：

状态定义为 $dp[i][j_{1}][j_{2}]$ 表示已经走过 $i$ 步，两个机器人的列号分别为 $j_[1], j_{2}$ 时，继续走到最后一行最多摘取的樱桃数。

这样定义的话，目标是 $dp[0][0][m-1]$，边界值为 $dp[n-1][j_{1}][j_{2}] = grid[n-1][j_{1}] + grid[n-1][j_{2}]$ （若 $j_{1} = j_{2}$ 则只记 1 次）。阶段按照 $i$ 从 $n-1$ 推导到 $0$，还是从边界值推导到目标。

目标只有一个，边界有很多个的情况，用记忆化搜索，从目标出发，即可简化实现过程。

状态转移方程

下面考虑状态转移方程，对于当前状态 $dp[i][j_{1}][j_{2}]$ 的过程，考虑它能从前一个阶段 ($i+1$) 的那些状态推导过来：

  • $j_{1}$ 可能从上一阶段的 $j_{1} - 1, j_{1}, j_{1} + 1$ 转移来。
  • $j_{2}$ 可能从上一阶段的 $j_{2} - 1, j_{2}, j_{2} + 1$ 转移来。

因此状态转移方程为：

1
2
3
4
5
6
7
8
9
10
11
dp[i][j1][j2] = grid[i][j1] + grid[i][j2]
                + max(dp[i + 1][j1 - 1][j2 - 1]
                     ,dp[i + 1][j1 - 1][j2]
                     ,dp[i + 1][j1 - 1][j2 + 1]
                     ,dp[i + 1][j1][j2 - 1]
                     ,dp[i + 1][j1][j2]
                     ,dp[i + 1][j1][j2 + 1]
                     ,dp[i + 1][j1 + 1][j2 - 1]
                     ,dp[i + 1][j1 + 1][j2]
                     ,dp[i + 1][j1 + 1][j2 + 1]
                     )

上述方程中，还需要注意 j1 = j2 时 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
class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        dp = vector<vector<vector<int>>>(rows, vector<vector<int>>(cols, vector<int>(cols, -1)));
        return solve(grid, 0, 0, cols - 1);
    }

private:
    vector<vector<vector<int>>> dp;
    int d_col[3] = {-1, 0, 1};

    int solve(const vector<vector<int>>& grid, int i, int j1, int j2)
    {
        if(dp[i][j1][j2] != -1)
            return dp[i][j1][j2];
        int rows = grid.size(), cols = grid[0].size();
        dp[i][j1][j2] = 0;
        int cur = grid[i][j1];
        if(j2 != j1)
            cur += grid[i][j2];
        if(i == rows - 1)
            return dp[i][j1][j2] = cur;
        for(int d1 = 0; d1 < 3; ++d1)
            for(int d2 = 0; d2 < 3; ++d2)
            {
                if(j1 + d_col[d1] < 0 || j1 + d_col[d1] >= cols)
                    continue;
                if(j2 + d_col[d2] < 0 || j2 + d_col[d2] >= cols)
                    continue;
                dp[i][j1][j2] = max(dp[i][j1][j2], cur + solve(grid, i + 1, j1 + d_col[d1], j2 + d_col[d2]));
            }
        return dp[i][j1][j2];
    }
};
Share