动态规划问题：计算K步从(0,0)到(x,y)的机器人路径方案数

机器人从x-y坐标系原点(0, 0)出发，仅能执行以下4种移动命令，每条命令对应1单位距离的移动：

• WEST：坐标变为(x-1, y)（x轴负方向）
• SUD：坐标变为(x, y-1)（y轴负方向）
• OST：坐标变为(x+1, y)（x轴正方向）
• NORD：坐标变为(x, y+1)（y轴正方向）

一个移动计划由上述命令的序列构成。给定目标坐标(x, y)和自然数K，计算恰好使用K条命令且能从(0,0)到达(x,y)的不同计划的数量。

核心边界条件 #

• 若K小于|x| + |y|，直接返回0：到达目标至少需要|x| + |y|步（沿直线移动），步数不足时不可能到达。
• 若K - (|x| + |y|)为奇数，也返回0：剩余步数需以“往返”形式抵消（如走一步再退回），只有偶数步才能完全抵消，否则无法停在目标点。

算法思路 #

1. 先执行边界判断，不满足条件直接返回0。
2. 计算剩余可用于往返的步数：m = (K - |x| - |y|) / 2，m为往返的组数（每组2步）。
3. 遍历所有可能的往返分组：设a为x轴往返组数，b为y轴往返组数（a + b = m）。
4. 对每种分组，用组合数计算该情况下的计划数量：
   • 从K步中选|x| + a步用于x轴（|x|步为目标方向，a步为反向）
   • 从这些x轴步数中选|x|步作为目标方向
   • 从剩余步数中选|y| + b步用于y轴（|y|步为目标方向，b步为反向）
   • 从这些y轴步数中选|y|步作为目标方向
5. 累加所有分组的数量，得到总计划数。

C风格伪代码 #

// 计算组合数C(n, k)，n >= k >= 0时返回结果，否则返回0
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    k = k < n - k ? k : n - k; // 利用组合数对称性减少计算量
    long long result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * (n - k + i) / i;
    }
    return result;
}

// 计算符合要求的移动计划数量
long long countRobotPlans(int x, int y, int K) {
    int dx = abs(x);
    int dy = abs(y);
    
    // 边界条件判断
    if (K < dx + dy || (K - dx - dy) % 2 != 0) {
        return 0;
    }
    
    int m = (K - dx - dy) / 2;
    long long total = 0;
    
    // 遍历所有可能的往返分组情况
    for (int a = 0; a <= m; ++a) {
        int b = m - a;
        long long c1 = comb(K, dx + a);
        long long c2 = comb(dx + a, dx);
        int remaining = K - (dx + a);
        long long c3 = comb(remaining, dy + b);
        long long c4 = comb(dy + b, dy);
        
        total += c1 * c2 * c3 * c4;
    }
    
    return total;
}

伪代码说明 #

• comb函数通过循环递推计算组合数，使用long long避免溢出，同时利用组合数对称性减少计算步骤。
• countRobotPlans函数先处理边界判断，再遍历所有往返分组的可能，累加每种情况的计划数量，最终返回总结果。

内容的提问来源于stack exchange，提问作者natik