【动态规划】 leet 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

此题同【动态规划】机器人达到指定位置方法数基本一样，不同在于边界条件的处理上，上一题是到1，回到2，到达N回到 N-1，本题的可以在数轴上面无限移动，由于startPos取值【1，1000】，k取值在【1，1000】，

所以最左边的位置是left= 1-1000+1=-998.

最右边的位置是 right=1000+1000-1=1999；

i取值范围【left，right】

所以本题也可以参照动态规划公式：dp[k][i]=dp[k-1][i-1]+dp[k-1][i+1]，考虑把整个位置向右平移1000，

动态规划的公式变成：dp[k][i+V]=(dp[k-1][i+V-1]+dp[k-1][i+V+1])%m; //X=1000

startPos=startPos+1000，endPos=endPos+1000，这样位置不会移动到负值，答案也是一样的。

代码：

   public int numberOfWays(int startPos, int endPos, int K) {
        int m=(int)1e9+7;
        int left=-998;  //1-1000+1=-998
        int right=1999; //1000+1000-1=1999
        int X=1000;
        int[][] dp = new int[K+1][right-left+X];

        dp[0][startPos+X] = 1;
        for (int k = 1; k <= K; k++) {
            for(int i=left;i<=right;i++){
                dp[k][i+X]=(dp[k-1][i+X-1]+dp[k-1][i+X+1])%m;
            }
        }
        return dp[K][endPos+X];
    }

本题类似题目：

【动态规划】机器人达到指定位置方法数