没搞过算法竞赛,不知道我的想法对不对
对于第一个问题,的确就是个动态规划,假设左下角坐标为(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))