5

您位于位置 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)。

我被困在如何使用帕斯卡三角形来解决它。这是正确的方法吗？我已经尝试过蛮力，但它太慢了。

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]
4

3 回答 3

2

您可以使用您提供的公式解决一维问题。

让我们H[pos][step]使用给定的步数来水平移动的方法数。
并且V[pos][step]是在给定步数的情况下移动垂直唱歌的多种方式。

您可以迭代将成为水平的步i = 0..M
数移动方式数H[x][i]*V[y][M-i]*C[M][i]，其中 C 是二项式系数。

您可以构建 H 和 VO(max(dx,dy)*M)并在O(M).

编辑： 关于 H 和 V的说明。假设你有行，有 d 个单元格：1,2,...,d。然后，您站在单元格编号 pos 处T[pos][step] = T[pos-1][step-1] + T[pos+1][step-1]，因为您可以向前或向后移动。

基本情况是T[0][step] = 0, T[d+1][step] = 0, T[pos][0] = 1。

我们建立 H 假设d = dx和 V 假设d = dy。

编辑2：基本上，算法的想法是因为我们在二维之一中移动并且检查也独立地基于每个维度，我们可以将二维问题拆分为2个一维问题。

于 2012-05-30T09:08:24.357 回答
0

一种方法是 O(n^3) 动态规划解决方案：

准备一个 3D 数组：

int Z[dx][dy][M]

其中 Z[i][j][n] 保存从位置 (i,j) 开始到最后 n 次移动的路径数。

基本情况是 Z[i][j][0] = 1 对于所有 i, j

递归情况是 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 后丢弃每个二维数组。

于 2012-05-30T08:58:45.493 回答
0

这是我为原始hackerrank问题构建的Java 解决方案。因为大网格永远运行。可能需要一些聪明的数学。

long compute(int N, int M, int[] positions, int[] dimensions) {
    if (M == 0) {
        return 1;
    }
    long sum = 0;
    for (int i = 0; i < N; i++) {
        if (positions[i] < dimensions[i]) {
            positions[i]++;
            sum += compute(N, M - 1, positions, dimensions);
            positions[i]--;
        }
        if (positions[i] > 1) {
            positions[i]--;
            sum += compute(N, M - 1, positions, dimensions);
            positions[i]++;
        }
    }
    return sum % 1000000007;
}
于 2016-07-05T20:02:27.073 回答