给定一个大小为NxN的正方形网格，每个单元格是空的或有障碍物的，只阻塞一个单元格，以尽量减少从左上角到右下角的路径数。你只允许向下或向右移动一步。阻塞一个单元格后，计算从左上角到右下角的路径数。总是至少有3个空单元格。其中两个总是开始和结束单元格，另一个可以是剩余单元格中的任何一个。
计算从左上角到右下角的路径数的部分相当容易，并且可以使用动态规划轻松解决。
我陷入困境的部分是要阻止的一个单元格以最小化路径数。直觉说要水平搜索网格并阻止具有最大传入和传出路径数的第一个单元格。例如网格
..## -> Row 1
..##
....
.... -> Row 4
我会阻塞（3,2），因为这将阻塞大部分路径，而剩余路径的数量将只有一条。但我不完全相信这是正确的方法。有什么见解吗？
计算从左上角到右下角的路径数量的部分相当容易，并且可以使用动态规划轻松解决
这个算法是一个很好的起点。考虑它的实现，它使用一个数组path sFromStart[N][N]来存储从起点到（row， co）的点的路径数。再次运行算法，但现在从最后开始。这给了你第二个二维数组，path sFromFinish[N][N]。
有了这两个数组，你就可以找到最初问题的答案了：如果（row， coll）上的一个点从开始有X条路径指向它，从结束有Y条路径指向它，那么通过删除该点可以切割的路径总数将是XY。遍历网格上的所有点，不包括开始、结束和已经被阻塞的点，并用
MAX(pathsFromStart[row][col]*pathsFromFinish[row][col])
