Leetcode 2400. Number of Ways to Reach a Position After Exactly k Steps

[Woodyiiiiiii]

这道题有点像我之前看过的机器人DP题。

DP的O(k ^ 2)解法：

1. 用二维数组模拟走势，第一位表示试验的次数，第二位表示所在位置
2. 可结合startPos和k得知最远距离，从而模拟限定范围

class Solution {
    public int numberOfWays(int startPos, int endPos, int k) {
        final long MOD = 1000000007;
        int n = k << 2 + 1;
        int diff = Math.abs(endPos - startPos);
        if (k < diff) {
            return 0;
        } else if (k == diff) {
            return 1;
        }
        
        long[][] dp = new long[k + 1][n];
        dp[0][k] = 1;

        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dp[i][j] != 0) {
                    if (j - 1 >= 0) {
                        dp[i + 1][j - 1] += dp[i][j];
                        dp[i + 1][j - 1] %= MOD;
                    }
                    if (j + 1 < n) {
                        dp[i + 1][j + 1] += dp[i][j];
                        dp[i + 1][j + 1] %= MOD;
                    }
                }
            }
        }

        return (int) dp[k][k + (endPos - startPos)];
    }
}

时隔两三个月后重新做了一遍，发现关键是：把k当做变量形成二维DP数组，有点类似我刚学习DP时的机器人移动的题目了。

---

• https://leetcode.com/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/