如何为一般情况编写伪代码？

Question

我将开始辅导，所以决定从我的算法课程中解决一些旧问题。问题如下：

你在卖报纸，并且每天你从一个十字路口开始你的行程，结束于你开始的东北方向。城市街道是网格状的，如下图所示，你从(0,0)出发，终点为(n,m)。

向北移动将把你从(x, y)带到(x, y +1)。向东移动将把你从(x, y)带到(x +1, y)。在每个交叉口(x, y)处，你停下来卖报纸，并且将获得收益r(x, y)。让OPT(n,m)表示从(0,0)到(n,m)的最优路径的总收益。

我使用自底向上的动态规划写了以下伪代码：

Bottom-Up-Alg(n,m,s[][]) \\ n and m are coordinates and s holds the revenue at each coordinate (n,m) 
opt = 0      \\ holds optimal revenue
opt += s[0][0] \\value at (0,0)
i = 0
j = 0
while (i <= n and j <= m)
    if (s[i+1][j] > s[i][j+1])
        opt += s[i+1][j]    \\ Move east
        i++
    else
        opt += s[i][j+1]     \\ Move north
        j++
return r

严格来说，该算法的运行时间为O(n+m)。但如果n和m成比例，则可以将其运行时间称为O(n)或O(m)。

问题在于，我发现我的算法是贪心的，并且它并不适用于每种情况。我很难编写泛化的伪代码。

- user101279

Answer 1

您可以对每个节点进行编号，从右上角节点开始，编号为从该节点开始时您可以获得的最大收益，以及给出该最大收益的前一个节点。O(nm)。

通过从右上到左下扫描对角线来完成此操作。

当此编号达到左下角时，您就得到了答案。只需回溯即可。

22 19-17-15--9
    |
27 26 17 16 14
    |
35-32 22 22 20

新增：如果你想知道如何扫描对角线，那么它比编码更容易可视化。

以下是一些C语言代码：

for (j = m-1; j >= -(n-1); j--){
  for (ii = n-1; ii >= 0; ii--){
    int jj = j + (n-1) - ii;
    int rii = rjj = 0;
    if (jj >= 0 && jj < m){
      if (ii+1 < n && jj   >= 0 && jj < m)
        rii = r[ii+1][jj];
      if (jj+1 < m && jj+1 >= 0)
        rjj = r[ii][jj+1];
      r[ii][jj] = s[ii][jj] + max( rii, rjj );
    }
  }
}

基本上，ii 和 jj 是你正在处理的单元格的索引，如果它的右侧或上方的邻居在矩形外部，则将其收入视为零。

- Mike Dunlavey

Answer 2

我是你的助手。我注意到这个问题是在作业截止日期之前发布的。现在已经过了截止日期，所以你要找的答案如下：

BOTTOM-UP-NEWSPAPER(n,m,r)
  opt = array(n,m)
  for i = 0 to n
    for j = 0 to m
      if i = 0 and j = 0      // In starting position
        opt[i][j] = r(i,j)
      else if i = 0 and j > 0 // On the south side of grid
        opt[i][j] = r(i,j) + opt[i][j-1]
      else if j = 0 and i > 0 // On the west side of grid
        opt[i][j] = r(i,j) + opt[i-1][j]
      else                    // Anywhere else
        opt[i][j] = r(i,j) + max(opt[i-1][j], opt[i][j-1])
  opt[n][m] holds the maximum revenue

- Aaron Okano

---

我很抱歉我没有把这个当作家庭作业识别出来。对不起。 - Mike Dunlavey

Answer 3

你的算法之所以能够运行，是因为它类似于 Dijkstra 算法，但其作用是在一个有向无环图中寻找最长路径，其中每个节点都有两条有向边。该算法采用贪心方式来查找关键路径。

该算法的运行时间应为 O(mn)，就像编辑距离的回溯过程一样。

- sereneL