Medium

题目描述

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

给定一个正整数 k，返回从 startPos 出发，恰好经过 k 步到达位置 endPos 的不同方案数。由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

如果步骤的顺序不完全相同，则认为两种方案是不同的。

注意数轴包含负整数。

示例 1：

输入：startPos = 1, endPos = 2, k = 3
输出：3
解释：从位置 1 恰好用 3 步到达位置 2 有以下 3 种方法：
- 1 -> 2 -> 3 -> 2
- 1 -> 2 -> 1 -> 2  
- 1 -> 0 -> 1 -> 2

示例 2：

输入：startPos = 2, endPos = 5, k = 10
输出：0
解释：无法从位置 2 恰好用 10 步到达位置 5。

约束条件：

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

解题思路

这是一个典型的组合数学问题。关键是理解问题的数学本质：

分析过程：

  1. 设向右走 right 步，向左走 left 步，则 right + left = k
  2. 净移动距离为 right - left = endPos - startPos
  3. 解这个方程组：right = (k + endPos - startPos) / 2，left = (k - endPos + startPos) / 2

可行性判断：

  • right 和 left 都必须是非负整数
  • k 和 endPos - startPos 的奇偶性必须相同（否则无解）
  • |endPos - startPos| <= k（距离不能超过总步数）

方案数计算： 一旦确定了向右和向左的步数，问题就转化为：在 k 步中选择 right 步向右走的组合数，即 C(k, right)。

使用动态规划方法计算组合数可以避免大数溢出和提高效率。状态转移方程为：C(n, r) = C(n-1, r-1) + C(n-1, r)。

代码实现

class Solution {
public:
    int numberOfWays(int startPos, int endPos, int k) {
        const int MOD = 1e9 + 7;
        int diff = abs(endPos - startPos);
        
        // 检查可行性
        if (diff > k || (k - diff) % 2 != 0) {
            return 0;
        }
        
        int right = (k + diff) / 2;
        
        // 计算组合数 C(k, right)
        vector<vector<long long>> dp(k + 1, vector<long long>(right + 1, 0));
        
        // 初始化
        for (int i = 0; i <= k; i++) {
            dp[i][0] = 1;
        }
        
        // 填表
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= min(i, right); j++) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
            }
        }
        
        return dp[k][right];
    }
};

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD = 10**9 + 7
        diff = abs(endPos - startPos)
        
        # 检查可行性
        if diff > k or (k - diff) % 2 != 0:
            return 0
        
        right = (k + diff) // 2
        
        # 计算组合数 C(k, right)
        dp = [[0] * (right + 1) for _ in range(k + 1)]
        
        # 初始化
        for i in range(k + 1):
            dp[i][0] = 1
        
        # 填表
        for i in range(1, k + 1):
            for j in range(1, min(i, right) + 1):
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD
        
        return dp[k][right]

public class Solution {
    public int NumberOfWays(int startPos, int endPos, int k) {
        const int MOD = 1000000007;
        int diff = Math.Abs(endPos - startPos);
        
        // 检查可行性
        if (diff > k || (k - diff) % 2 != 0) {
            return 0;
        }
        
        int right = (k + diff) / 2;
        
        // 计算组合数 C(k, right)
        long[,] dp = new long[k + 1, right + 1];
        
        // 初始化
        for (int i = 0; i <= k; i++) {
            dp[i, 0] = 1;
        }
        
        // 填表
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= Math.Min(i, right); j++) {
                dp[i, j] = (dp[i-1, j-1] + dp[i-1, j]) % MOD;
            }
        }
        
        return (int)dp[k, right];
    }
}

var numberOfWays = function(startPos, endPos, k) {
    const MOD = 1e9 + 7;
    const diff = Math.abs(endPos - startPos);
    
    // 检查可行性
    if (diff > k || (k - diff) % 2 !== 0) {
        return 0;
    }
    
    const right = Math.floor((k + diff) / 2);
    
    // 计算组合数 C(k, right)
    const dp = Array(k + 1).fill(null).map(() => Array(right + 1).fill(0));
    
    // 初始化
    for (let i = 0; i <= k; i++) {
        dp[i][0] = 1;
    }
    
    // 填表
    for (let i = 1; i <= k; i++) {
        for (let j = 1; j <= Math.min(i, right); j++) {
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
        }
    }
    
    return dp[k][right];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(k²)需要填充大小为 k×right 的动态规划表，其中 right ≤ k
空间复杂度O(k²)存储动态规划表所需的空间

相关题目