目前还不清楚农民必须采取相同的回合数，所以让我们假设在每次迭代中，我们有多达6个选项：农民1向下_左、下、右下移动，农民2也是如此。
当农民处于边缘或底部时，计数可以小于6。
请注意，没有循环。每个农民最终都会使MAX_ROWS-1向下移动。
解决方案涉及递归。
考虑 * 状态 *：

• int grid[MAX_ROWS][MAX_COLS]
• int farmer_row[2]; int farmer_col[2]
• int move_count（初始值为0）
• int move[(MAX_ROWS - 1) * 2]来记录6步中的哪一步。（无需初始化）
• 苹果总数
• 最佳苹果总数
• 最佳移动列表。

1.初始化状态
1.调用递归function(state)。
尝试每一个6移动保持跟踪，如果至少有一个是法律的。
B.对于每一步：走一步并记录下最好的一步，（最大的苹果和-递归返回值）。返回值-1表示递归未能达到法律的结束状态。
C.如果在最后一步和苹果总和比最好的苹果总和好，复制总和和移动列表到最好的。
D.每次移动：撤消移动的效果。
E.如果没有找到法律的移动返回-1，否则返回最佳和。
1.报告最好的总和和移动列表。
更高级的方法将预先计算每行最高的2棵树的总和，并在检查6种可能的移动和当前总和时使用。如果每个农民的当前和+剩余行中最好的2行小于先前移动的和，则不需要递归该移动。

解决这个问题的一种方法可能是同时考虑这两种立场。
Python代码：

def valid(l, r, n):
  return 0 <= l < n and 0 <= r < n and l <= r

def moves(l, r, n):
  candidates = [
    (l, r - 1),
    (l, r),
    (l, r + 1),
    (l - 1, r - 1),
    (l - 1, r),
    (l - 1, r + 1),
    (l + 1, r - 1),
    (l + 1, r),
    (l + 1, r + 1)
  ]
  return filter(lambda lr: valid(lr[0], lr[1], n), candidates)
    

def f(grid):
  m = len(grid)
  n = len(grid[0])
  dp = {
    (0, 0): grid[0][0] + grid[0][n-1]
  }
  for row in range(1, m):
    dp2 = {}
    for (l, r) in dp:
      for (ll, rr) in moves(l, r, n):
        count = grid[row][ll] + (
          grid[row][rr] if rr != ll else 0)
        new_total = dp[(l, r)] + count 
        if (ll, rr) in dp2:
          dp2[(ll, rr)] = max(
            dp2[(ll, rr)], new_total)
        else:
          dp2[(ll, rr)] = new_total
    dp = dp2
  return max(dp.values())

grid = [
  [3, 1, 1],
  [5, 6, 2],
  [9, 6, 7]
]

print(f(grid)) # 31