路径只能从（0,0）开始在网格中向左和向下移动。最终它需要到达（N-1， N-1）。
如果网格是NxN，则有2N选择N条这样的路径，随着N的增加呈指数增长，由于内存限制，我无法将所有这些路径存储在列表中。我们还可以将每个路径编码为长度为2^（N-1）的位串，其中1是向右移动，0是向下移动。每个编码路径中有相等数量的0和1。
我得到了一个维度为NxN的二维正方形网格。网格中的每个单元格都有一个非负值。我需要为每个唯一路径求和所有这些值。我如何有效地做到这一点？
让我们将值矩阵称为V，因此V[y][x]是单元格（x， y）处的值。
每条路径从（0,0）开始，到（N-1，N-1）结束。路径P的总值，value（P）是位于P上的所有单元格的值之和。
问题是计算从（0,0）到（N-1，N-1）的所有有效路径P的SUM（值（P））。
计算SUM的另一种方法不是枚举每个有效路径，而是计算每个单元格（x， y）有多少路径穿过这个单元格。如果有i条路径穿过这个单元格，那么这个单元格贡献的总价值是i*V[y][x]。因此，我们只需遍历网格中的每个单元格，为其计算i（x，y），将i（x，y）*V[y][x]添加到总结果中。
如何计算i（x， y）？i（x，y）只是有效路径的数量。从（0,0）到（N-1，N-1）通过（x，y）。提示：-如果有a种方法可以从（0,0）到达（x，y），b种方法可以从（x，y）到达（N-1，N-1），那么有a*b种方法可以通过（x，y）从（0,0）到达（N-1，N-1）。Rest很容易。
