你有一个包含一组正数和负数的NxN网格，你必须找到通过它的最佳路径。路径必须只穿过每行中的一个单元格，并且相邻行上的单元格必须垂直或对角线连接。你能找到一种算法来解决这个问题而不评估每个排列吗？
我假设"最佳路径"被定义为总和最高的路径？
您可以使用动态规划。对于每一行，将该行的元素设置为以该行结尾的最佳路径值。所以
solution[i][j] = grid[i][j] + max(solution[i-1][j], solution[i-1][j-1], solution[i-1][j+1])
当然要考虑到边界条件。初始条件是：
solution[0][j] = grid[0][j]
您还需要跟踪最佳路径所采用的实际路径（选择了哪些网格元素）。到达最后一行后，浏览该行并找到最大值。这将为您提供最佳路径及其价值。