algorithm - 查找可以从网格中收集的最大黄金量

给定一个m*n大小的网格。网格中的每个块都有一定数量的黄金。
我们从网格的第一列（任何行）开始，只能在3个方向上移动-右上（左对角线）和右下（右对角线）。
我们可以从网格中收集到最多的黄金量。
我试过使用具有以下递归关系的动态规划
dp[i][j]=max{a[i-1][j+1]，a[i][j+1]，a[i+1][j+1]}+a[i][j]对于j=0到n-1
当i=m时，dp[i][j]=0
这会给出正确和最佳的答案吗？

最佳答案

让

d[i][j]

黄金是最大的黄金，可以从位置“CC”开始，通过右、右、上、右移动，对于任何(i,j)，i in [0..m-1]。我们得到了如下的递推关系，即访问j in [0..n-1]和[0..m-1]之外的坐标意味着返回[0..n-1]。

d[i][j] = a[i][j] + max { d[i  ][j+1], // right
                          d[i-1][j+1], // right up
                          d[i+1][j+1]  // right down
                        }

这里的问题是使用一个评估序列，对于这个序列，0表达式中出现的每个所需的d值都可用于max的评估评价顺序必须在最右边的列开始，对每个d[i][j]设置d[i][n-1] = a[i][n-1]，国家必须从右到左填充柱；经过评估，最适宜的金量是在最左边的列中出现的最大值。