算法动态规划

状态计算的方向：从已知状态计算当前状态；从当前状态更新后续状态

字数统计: 3.4k字   |   阅读时长: 14分
,

摘要: 状态计算的方向的影响

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

在动态规划中，当状态表示和阶段划分给定，状态转移方程可以有两个方向的写法可以选，分别对应不同的考虑方式，一个是考虑从先前阶段的已知状态如何计算当前状态，也就是当前状态可以从哪些状态转移过来；另一个是考虑从当前状态如何更新后续阶段的未知状态，也就是当前状态可以转移到哪些状态。

以下面的 DAG 上的 DP 为例，在考虑节点 5 的状态计算的时候：

  • 如果考虑从先前阶段的已知状态如何计算当前状态，则需要将前面阶段的节点 1、2、3 均计算完，然后再计算当前状态 5；
  • 如果考虑从当前状态如何更新后续阶段的未知状态，则将后续阶段的状态 7、8、9 中，把当前状态 5 的贡献加入进去。

DAG 上的 DP

一般来讲这两种方式没什么差别。只是在有的问题中，其中一种可能会比另一种考虑起来更自然一点。

本文通过青蛙过河问题来看看状态定义的方向以及状态转移方程的方向的问题。

青蛙过河问题

403. 青蛙过河

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

示例 1：
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

示例 2：
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

提示：

1
2
3
4
2 <= stones.length <= 2000
0 <= stones[i] <= 2^31 - 1
stones[0] == 0
stones 按严格升序排列

动态规划要素

阶段

石子位置列表是严格递增的，因此我们可以考虑根据石子位置列表划分阶段。

假设当前在第 $i$ 个石子处，选择一个可以跳到的石子，跳过去，进入下一阶段。

附加信息

要知道下一步可以跳跃的范围，需要知道上一步的跳跃距离 $k$，因此阶段不足以表示状态，需要一个附加信息 $k$，有了这个附加信息，我们就知道下一步的跳跃距离只能是 $k - 1, k, k + 1$ 这三个之一。

经过推导还可以发现，如果某一步挑了 $k$ 距离，则其上一步也只能是 $k - 1, k, k + 1$ 之一。

状态表示

方向1：$(1, 1)$ 作为边界，$(n-1, k), 1\leq k < n$ 作为目标

根据前面的阶段和附加信息的分析，我们写出状态表示：$dp[i][k]$，表示从 $(0, 0)$ 出发，能否在最后一步跳跃距离为 $k$ 的情况下到达第 $i$ 个石子处。如果能则为 $1$，不能则为 $0$。其中 $i$ 是阶段，$k$ 是附加状态。

这样定义的话，目标是 $dp[n-1][\cdots]$ 中是否有一个 $1$；边界为：若 $dp[1][1] = 1$，(如果不满足 $stones[1] = 1$，则第一步都无法走，直接返回 false。)

阶段的推导方向是 $i$ 从 $0$ 逐渐变大到 $n-1$ (有可能额会跳着走)，也就是从边界值向目标方向推导，附加状态 $k$ 的推导顺序不重要，无后效性已经由阶段保证。

方向2：$(0, 1)$ 作为目标，$(n-1, k), 1\leq k < n$ 作为边界

状态表示还可以反方向定义：$dp[i][k]$，表示从第 $1$ 个石子出发，下一步跳跃距离 $k$ 的情况下，能否到达第 $n-1$ 个石子处。如果能则为 $1$，不能则为 $0$。其中 $i$ 是阶段，$k$ 是附加状态。

这样定义的话，目标是 $dp[0][1]$，边界值是 $dp[n-1][k] = 1, 1\leq k < n$。

阶段的推导方向是 $i$ 从 $n-1$ 逐渐减小到 $0$ (有可能跳着走)，依然是从边界值向目标方向推导。附加状态 $k$ 的推导顺序不重要，无后效性已经由阶段保证。

可以看到，状态定义的方向决定了哪一端作为边界值，哪一端作为目标。而阶段的推导始终是从边界值向目标推导。

定义好状态之后可能出现边界值只有一个，而目标非常多；或者边界值有很多，而目标只有一个的情况。如果能恰当选取状态计算的方向，可以简化实现过程。

下面以采用前面的第一种状态定义方式为例，看一下状态计算的不同方向、以及递推和记忆化搜索有什么区别。

状态转移方程：从已知状态计算当前状态

考虑如何从先前阶段的已知状态计算当前状态 $dp[i][k]$，也就是当前状态可以从哪些状态转移过来。

如果从第 $j$ 个石头跳跃 $k$ 距离到达第 $i$ 个石头，也就是 $mapping[stones[i] - k] = j$，则当 $l\in\{k-1,k,k+1\}$ 时，$dp[j][l]$ 对 $dp[i][k]$ 有所贡献。

当所有上一阶段满足以上条件的相关状态 $dp[j][l]$ 都已经算完，当前状态的计算如下：

代码 (C++，递推)

按维度线性递推，状态计算顺序的正确性由阶段保证。

576 ms。

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
class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        if(stones[1] != 1)
            return false;
        if(n <= 2)
            return true;

        unordered_map<int, int> mapping;

        for(int i = 1; i < n; ++i)
            mapping[stones[i]] = i;

        // dp[i][k] := 从 (0, 0) 出发，能否在最后一步跳跃 k 的情况下到达第 $i$ 个石头。
        vector<vector<int>> dp(n, vector<int>(n + 1, 0)); 

        // 初始化
        dp[1][1] = 1;

        for(int i = 2; i < n; ++i)
        {
            // 第 i 阶段，k 的最大可能值为 i
            for(int k = 1; k <= i; ++k)
            {
                // 根据先前阶段的已知状态，计算状态 dp[i][k]
                if(mapping.count(stones[i] - k) == 0)
                    continue;
                // 枚举可能的 dp[j][l]
                int j = mapping[stones[i] - k];
                // 第 j 个点可以转移到第 i 个点
                for(int l: {k + 1, k, k - 1})
                {
                    if(l <= 0 && l >= n)
                        continue;
                    if(dp[j][l] == 1)
                    {
                        dp[i][k] = 1;
                        if(i == n - 1)
                            return true;
                        break;
                    }
                }
            }
        }

        return false;
    }
};

代码 (C++，记忆化搜索)

状态转移方程的方向是从已知状态更新当前状态，则记忆化搜索从目标出发。

52 ms。

目标很多的时候则每个目标都需要走一次记忆化搜索。因此可以反向状态定义，使得目标只有一个，使得记忆化搜索只需要走一次。

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
53
54
class Solution {
public:
    bool canCross(vector<int>& stones) {
        n = stones.size();
        if(stones[1] != 1)
            return false;
        if(n <= 2)
            return true;

        for(int i = 1; i < n; ++i)
            mapping[stones[i]] = i;

        dp = vector<vector<int>>(n, vector<int>(n + 1, -1)); 
        // 初始化
        dp[1][1] = 1;
        for(int k = 2; k < n; ++k)
            dp[1][k] = 0;

        for(int k = 1; k < n; ++k)
        {
            if(solve(n - 1, k, stones) == 1)
                return true;
        }

        return false;
    }

private:
    unordered_map<int, int> mapping; // 石头 -> 下标
    // dp[i][k] := 当前在第 i 个石子 stones[i], 上一步跳 k 步，能否达到 stones[n - 1]
    vector<vector<int>> dp; 
    int n;

    int solve(int i, int k, const vector<int>& stones)
    {
        if(dp[i][k] != -1)
            return dp[i][k];

        if(mapping.count(stones[i] - k) == 0)
            return dp[i][k] = 0;

        // 枚举可能的 dp[j][l]
        int j = mapping[stones[i] - k];
        for(int l = k - 1; l <= k + 1; ++l)
        {
            if(l <= 0 || l >= n) 
                continue;
            if(solve(j, l, stones) == 1)
                return dp[i][k] = 1;
        }

        return dp[i][k] = 0;
    }
};

状态转移方程：从当前状态更新未知状态

考虑从当前状态 $dp[i][k]$ 如何更新后续阶段的未知状态，也就是当前状态经过一次决策可以转移到哪些状态。

如果从第 $i$ 个石头跳跃 $l\in\{k-1,k,k+1\}$ 距离到达第 $j$ 个石头，也就是 $mapping[stones[i] + l] = j$，则 $dp[i][k]$ 对 $dp[j][l]$ 有所贡献，如下：

代码 (C++，递推)

按维度线性递推，状态计算顺序的正确性由阶段保证。

172 ms。

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
class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        if(stones[1] != 1)
            return false;
        if(n <= 2)
            return true;

        unordered_map<int, int> mapping;

        for(int i = 1; i < n; ++i)
            mapping[stones[i]] = i;

        // dp[i][k] := 从 (0, 0) 出发，能否在最后一步跳跃 k 的情况下到达第 $i$ 个石头。
        vector<vector<int>> dp(n, vector<int>(n + 1, 0)); 

        // 初始化
        dp[1][1] = 1;

        for(int i = 1; i < n - 1; ++i)
        {
            // 第 i 阶段，k 的最大可能值为 i
            for(int k = 1; k <= i; ++k)
            {
                if(dp[i][k] == 0)
                {
                    // dp[i][k] = 0 则由状态转移方程，对 d[j][l] 无修改
                    continue;
                }
                // 由当前状态 dp[i][k] 更新后续阶段的状态
                for(int l: {k + 1, k, k - 1})
                {
                    if(mapping.count(stones[i] + l) == 0)
                        continue;
                    // 枚举可能的后续状态 dp[j][l]
                    int j = mapping[stones[i] + l];
                    dp[j][l] = 1;
                    if(j == n - 1)
                        return true;
                }
            }
        }

        return false;
    }
};

代码 (C++，记忆化搜索)

状态转移方程的方向是从当前状态更新未知状态，则记忆化搜索从边界值出发。

在递归地更新 $dp$ 的过程中，考虑当前状态 $dp[i][k]$ 对下一阶段状态 $dp[j][l]$ 造成影响：

  • 如果 $dp[j][l]$ 有修改，则后续阶段的状态的贡献需要递归地去更新。
  • 如果 $dp[j][l]$ 无修改，则不用递归地更新后续阶段的状态。

72ms

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
class Solution {
public:
    bool canCross(vector<int>& stones) {
        n = stones.size();
        if(stones[1] != 1)
            return false;
        if(n <= 2)
            return true;

        for(int i = 1; i < n; ++i)
            mapping[stones[i]] = i;

        dp = vector<vector<int>>(n, vector<int>(n + 1, 0)); 

        // 初始化
        dp[1][1] = 1;
        iterative(1, 1, stones);

        for(int k = 1; k < n; ++k)
            if(dp[n - 1][k] == 1)
                return true;
        return false;
    }

private:
    unordered_map<int, int> mapping; // 石头 -> 下标
    // dp[i][k] := 当前在第 i 个石子 stones[i], 上一步跳 k 步，能否达到 stones[n - 1]
    vector<vector<int>> dp; 
    int n;

    void iterative(int i, int k, const vector<int>& stones)
    {
        if(i >= n)
            return;

        // 由当前状态 dp[i][k] 更新后续阶段的状态
        for(int l: {k + 1, k, k - 1})
        {
            if(l <= 0 || l >= n)
                continue;
            if(mapping.count(stones[i] + l) == 0)
                continue;
            // 枚举可能的后续状态 dp[j][l]
            int j = mapping[stones[i] + l];
            if(dp[j][l] == 0)
            {
                dp[j][l] = 1;
                iterative(j, l, stones);
            }
        }
    }
};

总结

  • 状态定义的方向决定了哪一端作为初始值，哪一端作为目标。阶段的推导始终是从初始值向目标推导的。
  • 状态转移的方向决定了是用先前阶段的已知状态计算当前状态，还是从当前状态去更新后续阶段的未知状态。
  • 递推和记忆化搜索的状态推导顺序会有所不同：
  • 不同状态定义和状态计算的选取下，递推的实现方式基本一样，都是按维度线性推导，状态计算顺序的正确性由阶段来保证。
  • 如果状态定义和状态计算选取合适，记忆化搜索可能更简单：
    • 如果状态定义后，目标只有一个，边界比较零散，则从已知状态计算当前状态，用从目标出发的记忆化搜索的实现方式可能会更简单。
    • 如果状态定义后，边界只有一个，目标比较零散，则从当前状态更新后续状态，用从边界出发的记忆化搜索的实现方式可能会更简单。
Share