您位于x,y位置的网格中.行的尺寸为dx,dy.只需一步,您就可以在行或列中前进或后退一步.你有多少种方法可以采取M步,这样你就不会在任何时候离开网格？
您可以多次访问同一位置.
如果您对x,y x,y <= 0或x,y> dx,dy,则离开网格.
1 <= M <= 300
1 <= x,y <= dx,dy <= 100
输入:
M
xy
dx dy
输出:
没有方法
示例:
输入:
1
6 6
12 12
产量:
4
示例:
输入:
2
6 6
12 12
输出:
16
如果你在6,6位置,那么你可以步行到(6,5),(6,7),(5,6),(7,6).
我坚持如何使用Pascal的三角形来解决它.这是正确的方法吗？我已经尝试过蛮力,但速度太慢了.
C[i][j], Pascal Triangle
C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
T[startpos][stp]
T[pos][stp] = T[pos + 1][stp - 1] + T[pos - 1][stp - 1]