技术

记一道动态规划+数学期望的算法题

算法

最近碰到一个算法题，开始觉得很简单，后来觉得有点难，后来做了做发现其实没有那么难，感觉有点意思。在这里分享一下这道题和解题思路。
这道题的题目如下：

一个n*m的网格，每个格子上有三个参数pD,pR,pS。pD表示下一步走到下方格子的概率，pR表示下一步走到右方格子的概率，pS表示下一步仍然在原地的概率。0<= pD, pR, pS <=1，pD+pR+pS = 1。从左上角格子到右下角格子的步数期望是多少？

看到网格，从左上角走到右下角，第一反应这就是一道常规的动态规划。这个反应没错，那么接下来就是怎么去推导状态转移方程。

如果设$step(i, j)$为从左上角到$(i, j)$的步数期望，那么需要找到一种函数关系$f(x)$，使得：
$$step(i, j) = f(step(i-1, j), step(i, j-1))$$
注意题目中有个条件：就算停留在原地一次，也算走了一步。如果用传统的dp思维，那么从$(i-1, j)$和$(i, j-1)$到$(i, j)$的状态转移方程就十分复杂，因为可能在格子上无限停留，得先求和再求极限。并且从$(0,0)$到$(0,0)$的步数期望并不为0（因为可能在左上角一直停留，也算步数），这个问题就难解了。所以，要再想想有没有简单的方法。
如果我们设期望$E(i, j)$为从$(i, j)$到右下角的步数期望，那么问题就转换成从$E(n-1, m-1)$递推到$E(0, 0)$，而$E(n-1, m-1)$是肯定为0的，问题突然开始出现了转机。
那么，考虑到$E(i, j)$会原地不动，我们先不急着得到状态转移方程，先列一下$E(i, j)$和什么相关。首先，思路是从右下角开始往左上递推，那么和$E(i, j)$有关的就是$E(i+1, j)$和$E(i, j+1)$了，可以得出如下的方程：
$$E(i, j) = pD \times E(i+1, j) + pR \times E(i, j+1) + pS \times E(i, j) + 1$$
这个方程中，连$E(i, j)$自身都在等号右侧，我刚列出来的时候也感觉有点别扭，但这个题的核心就在这里要绕个弯。根据上面的方程，可以求出$E(i, j)$的通项为：
$$E(i, j) = \frac{pD \times E(i+1, j) + pR \times E(i, j+1) + 1}{1-pS}$$
对于处于边缘区域的最下面的一行和最右边的一列，是分别没有$E(i+1, j)$和$E(i, j+1)$的，那么他们就没有这两项。所以总结出来通项就是：
如果i=n-1且j=m-1, 则$E(i, j) = 0$
如果i=n-1，则$E(i, j) = \frac{pR \times E(i, j+1) + 1}{1-pS}$
如果j=m-1，则$E(i, j) = \frac{pD \times E(i+1, j) + 1}{1-pS}$
如果0<=i<n-1且0<=j<m-1，则$E(i, j) = \frac{pD \times E(i+1, j) + pR \times E(i, j+1) + 1}{1-pS}$

有了上面的思考和dp状态转移方程，代码就比较容易写了，这里我用Golang写了一个：

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
func solve(grid [][][3]float64) float64 {
    n := len(grid)
    if n == 0 {
        return 0
    }
    m := len(grid[0])
    dp := make([][]float64, n)
    for i:=n-1; i>=0; i-- {
        dp[i] = make([]float64, m)
        if i == n-1 {
            for j := m-2; j>=0; j-- {
                dp[n-1][j] = (dp[n-1][j+1]*grid[n-1][j][1] + 1) / (1-grid[n-1][j][2])
            }
        } else {
            dp[i][m-1] = (dp[i+1][m-1]*grid[i][m-1][0] + 1) / (1 - grid[i][m-1][2])
        }
    }

    for i:=n-2; i>=0; i-- {
        for j:=m-2; j>=0; j-- {
            toDown := grid[i][j][0]
            toRight := grid[i][j][1]
            stop := grid[i][j][2]
            dp[i][j] = (toDown*dp[i+1][j] + toRight*dp[i][j+1] + 1) / (1-stop)
        }
    }
    return dp[0][0]
}

其实按照上面的思路，正推也可以推出来。如果设$E(i, j)$为从左上角到$(i, j)$的步数期望，就会有：
$$E(i, j) = pD \times E(i-1, j) + pR \times E(i, j-1) + pS \times E(i, j) + 1$$
$E(0, 0)$会满足这个条件：
$$E(0, 0) = pS \times E(0, 0) + 1$$
按照上文的思路，把$E(i, j)$的通项求出，也能从左上角推导到右下角。

写完不得不感叹，动态规划的算法题真的是千变万化，需要开动脑筋多想想。

分享到