【算法题】2400. 恰好移动 k 步到达某一位置的方法数目-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法题】2400. 恰好移动 k 步到达某一位置的方法数目。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

给你两个正整数 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

思路：

动态规划，因为要考虑负数，再考虑k的范围，整体加上1000，dp[i+1000][j]表示到达位置i，花费j步的方案数。文章来源地址https://www.toymoban.com/news/detail-426588.html

java代码：

class Solution {
  int mod = (int) 1E9 + 7;

  public int numberOfWays(int startPos, int endPos, int k) {
    long[][] dp = new long[3005][1005];
    dp[startPos + 1 + 1000][1] = 1;
    dp[startPos - 1 + 1000][1] = 1;
    for (int i = 2; i <= k; i++) {
      for (int j = 1000 + startPos - k; j <= 1000 + startPos + k; j++) {
        dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
        dp[j][i] %= mod;
      }
    }
    return (int) dp[1000 + endPos][k];
  }
}

到了这里，关于【算法题】2400. 恰好移动 k 步到达某一位置的方法数目的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！