Question

2400. 恰好移动 k 步到达某一位置的方法数目

English Version

题目描述

给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。

给你一个正整数 k ，返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法数目。由于答案可能会很大，返回对 109 + 7 取余 的结果。

如果所执行移动的顺序不完全相同，则认为两种方法不同。

注意：数轴包含负整数。

 

示例 1：

输入：startPos = 1, endPos = 2, k = 3
输出：3
解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法：
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
可以证明不存在其他方法，所以返回 3 。

示例 2：

输入：startPos = 2, endPos = 5, k = 10
输出：0
解释：不存在从 2 到 5 且恰好移动 10 步的方法。

 

提示：

• 1 <= startPos, endPos, k <= 1000

解法

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j)$，表示当前位置距离目标位置的距离为 $i$，还剩 $j$ 步，有多少种方法到达目标位置。那么答案就是 $dfs(abs(startPos - endPos), k)$。

函数 $dfs(i, j)$ 的计算方式如下：

• 如果 $i \gt j$ 或者 $j \lt 0$，说明当前位置距离目标位置的距离大于剩余步数，或者剩余步数为负数，此时无法到达目标位置，返回 $0$；
• 如果 $j = 0$，说明剩余步数为 $0$，此时只有当前位置距离目标位置的距离为 $0$ 时才能到达目标位置，否则无法到达目标位置，返回 $1$ 或者 $0$；
• 否则，当前位置距离目标位置的距离为 $i$，还剩 $j$ 步，那么有两种方法到达目标位置：
  • 向左移动一步，此时当前位置距离目标位置的距离为 $i + 1$，还剩 $j - 1$ 步，方法数为 $dfs(i + 1, j - 1)$；
  • 向右移动一步，此时当前位置距离目标位置的距离为 $abs(i - 1)$，还剩 $j - 1$ 步，方法数为 $dfs(abs(i - 1), j - 1)$；
• 最后，返回两种方法的和对 $10^9 + 7$ 取余的结果。

为了避免重复计算，我们使用记忆化搜索，即使用一个二维数组 $f$ 记录函数 $dfs(i, j)$ 的结果，当函数 $dfs(i, j)$ 被调用时，如果 $f[i][j]$ 不为 $-1$，则直接返回 $f[i][j]$，否则计算 $f[i][j]$ 的值，并返回 $f[i][j]$。

时间复杂度 $O(k^2)$，空间复杂度 $O(k^2)$。其中 $k$ 为题目给定的步数。

class Solution:
  def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
    @cache
    def dfs(i: int, j: int) -> int:
      if i > j or j < 0:
        return 0
      if j == 0:
        return 1 if i == 0 else 0
      return (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod

    mod = 10**9 + 7
    return dfs(abs(startPos - endPos), k)

class Solution {
  private Integer[][] f;
  private final int mod = (int) 1e9 + 7;

  public int numberOfWays(int startPos, int endPos, int k) {
    f = new Integer[k + 1][k + 1];
    return dfs(Math.abs(startPos - endPos), k);
  }

  private int dfs(int i, int j) {
    if (i > j || j < 0) {
      return 0;
    }
    if (j == 0) {
      return i == 0 ? 1 : 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = dfs(i + 1, j - 1) + dfs(Math.abs(i - 1), j - 1);
    ans %= mod;
    return f[i][j] = ans;
  }
}

class Solution {
public:
  int numberOfWays(int startPos, int endPos, int k) {
    const int mod = 1e9 + 7;
    int f[k + 1][k + 1];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i > j || j < 0) {
        return 0;
      }
      if (j == 0) {
        return i == 0 ? 1 : 0;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      f[i][j] = (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod;
      return f[i][j];
    };
    return dfs(abs(startPos - endPos), k);
  }
};

func numberOfWays(startPos int, endPos int, k int) int {
  const mod = 1e9 + 7
  f := make([][]int, k+1)
  for i := range f {
    f[i] = make([]int, k+1)
    for j := range f[i] {
      f[i][j] = -1
    }
  }
  var dfs func(i, j int) int
  dfs = func(i, j int) int {
    if i > j || j < 0 {
      return 0
    }
    if j == 0 {
      if i == 0 {
        return 1
      }
      return 0
    }
    if f[i][j] != -1 {
      return f[i][j]
    }
    f[i][j] = (dfs(i+1, j-1) + dfs(abs(i-1), j-1)) % mod
    return f[i][j]
  }
  return dfs(abs(startPos-endPos), k)
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function numberOfWays(startPos: number, endPos: number, k: number): number {
  const mod = 10 ** 9 + 7;
  const f = new Array(k + 1).fill(0).map(() => new Array(k + 1).fill(-1));
  const dfs = (i: number, j: number): number => {
    if (i > j || j < 0) {
      return 0;
    }
    if (j === 0) {
      return i === 0 ? 1 : 0;
    }
    if (f[i][j] !== -1) {
      return f[i][j];
    }
    f[i][j] = dfs(i + 1, j - 1) + dfs(Math.abs(i - 1), j - 1);
    f[i][j] %= mod;
    return f[i][j];
  };
  return dfs(Math.abs(startPos - endPos), k);
}