找到可以从网格中收集的最大数量的黄金
Find maximum amount of gold that can can be collected from a grid
给定一个 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
dp[i][j]=0 对于 i<0 或 i>=m
这会给出正确的最佳答案吗？
让
d[i][j]
是从位置(i,j)开始只向右、右上和右下移动可以获得的最大金币数量，对于任何i in [0..m-1]、j in [0..n-1] .我们得到以下递归关系，这意味着访问 [0..m-1] 和 [0..n-1] 之外的坐标意味着 return 0.
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
}
这里的问题是使用一个计算序列，其中出现在 max 表达式中的每个需要的 d 值都可用于计算 d[i][j]。评估序列必须从最右边的列开始，通过为每个 i in [0..m-1]. 设置 d[i][n-1] = a[i][n-1] 状态必须从右到左按列填充；经过评估，最佳金量是出现在最左边一列的最大值。
给定一个 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 dp[i][j]=0 对于 i<0 或 i>=m
这会给出正确的最佳答案吗？
让
d[i][j]
是从位置(i,j)开始只向右、右上和右下移动可以获得的最大金币数量，对于任何i in [0..m-1]、j in [0..n-1] .我们得到以下递归关系，这意味着访问 [0..m-1] 和 [0..n-1] 之外的坐标意味着 return 0.
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
}
这里的问题是使用一个计算序列，其中出现在 max 表达式中的每个需要的 d 值都可用于计算 d[i][j]。评估序列必须从最右边的列开始，通过为每个 i in [0..m-1]. 设置 d[i][n-1] = a[i][n-1] 状态必须从右到左按列填充；经过评估，最佳金量是出现在最左边一列的最大值。