娱乐 （红包）算法挑战一则——到达终点的方法种类

[古代学者]

下意识求解，等等，我在哪？

[古代学者]

20 分钟前，reflectK说道:

你在SS同盟

没搞过算法竞赛，不知道我的想法对不对

对于第一个问题，的确就是个动态规划，假设左下角坐标为（0,0），右上角为(m,n)，那么对于任意的i(m>=i>0)，j(n>=j>0)，抵达(i,j)所有可能路线为P(i,j)，那么P(i,j)=P(i-1,j)+P(i,j-1)。

对于第二个问题，因为需要执行一次魔法操作，不妨假定在(i,j)处执行魔法操作，其中i,j不同时为0。假设P(i,j)表示从(0,0)到(i,j)的所有可能路线，Q(i,j)表示(i,j)到(m,n)的所有可能路线，H(i,j)表示在(i,j)处执行魔法操作后对应的全部路线，那么H(i,j) = P(i,j) * (Q(i-1,j)+Q(i,j-1))

[古代学者]

刚刚，古代学者说道:

没搞过算法竞赛，不知道我的想法对不对

对于第一个问题，的确就是个动态规划，假设左下角坐标为（0,0），右上角为(m,n)，那么对于任意的i(m>=i>0)，j(n>=j>0)，抵达(i,j)所有可能路线为P(i,j)，那么P(i,j)=P(i-1,j)+P(i,j-1)。

对于第二个问题，因为需要执行一次魔法操作，不妨假定在(i,j)处执行魔法操作，其中i,j不同时为0。假设P(i,j)表示从(0,0)到(i,j)的所有可能路线，Q(i,j)表示(i,j)到(m,n)的所有可能路线，H(i,j)表示在(i,j)处执行魔法操作后对应的全部路线，那么H(i,j) = P(i,j) * (Q(i-1,j)+Q(i,j-1))

对于第三个问题，如果经过A则必须经过B，那么所有可能路线是第一个问题的解减去经过A而没经过B的所有路径，设Pa0表示从原点到A所有可能路径，Pa表示从A到终点所有可能路径，Pab表示从A到B所有可能路径，Pb表示从B到终点左右可能路径，P为第一个问题的解，本问题解为Q，则Q = P - Pa0 * (Pa - Pa * Pab * Pb)

如果经过A则强制穿越到B，那么AB绑死，所以所有可能路径是第一个问题的解减去所有经过A的解，再加上原点到A的所有可能路径与B到终点所有可能路径的乘积

如果不能同时经过A和B，那么所有可能路径是第一个问题的解减去同时经过AB的所有路径，后者是所有从原点到A的路径、A到B所有路径、B到终点所有路径的乘积