您位于x，y位置的网格中。行的尺寸为dx，dy。在一个步骤中，您可以在行或列中向前或向后走一步。有多少种方法可以使m步在任何点都不离开网格？你可以多次访问同一个职位。
如果对于任何x，y，x，ydx，dy，则离开网格。
11输入：
米
X Y轴
右边乘以
输出：
没有办法
例子：
输入：
1个
6 6个
2012年
输出：
4个
例子：
输入：
2个
6 6个
2012年
输出：
16个
如果你在位置6，6，那么你可以走到（6，5），（6，7），（5，6），（7，6）。
我一直纠结于如何用帕斯卡三角形来解这个问题。这是正确的方法吗？我已经试过使用暴力，但速度太慢了。
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]
最佳答案
一种方法是o（n^3）动态编程解决方案：
准备三维阵列：
int Z[dx][dy][M]
其中z[i][j][n]保存从位置（i，j）开始到最后n个移动的路径数。
对于所有i，j，基本情况是z[i][j][0]=1
递归的情况是z[i][j][n+1]=z[i-1][j][n]+z[i+1][j][n]+z[i][j-1][n]+z[i][j+1][n%（只包括地图上的求和项）
一旦数组被填充，返回z[x][y][m]
为了节省空间，可以在使用每个二维数组后丢弃n个数组。