#yyds干货盘点# 动态规划专题：过河卒

1.简述：

棋盘上 A点有一个过河卒，需要走到目标 B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A 点 (0, 0)、B点(n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A点能够到达 B点的路径的条数，假设马的位置(x,y)是固定不动的，并不是卒走一步马走一步。

注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 

数据范围： ，马的坐标 

仅一行，输入 n,m,x,y 四个正整数。分别表示B点坐标和马的坐标

输出路径总数

输入：

6 6 3 3

输出：

6

输入：

5 4 2 3

输出：

3

输入：

2 5 3 5

输出：

1

2.代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int bx = scan.nextInt();
        int by = scan.nextInt();
        int mx = scan.nextInt();
        int my = scan.nextInt();
        //int型在20 * 20 棋盘会超
        long[][] dp = new long[bx + 1][by + 1];
        // 判断马在棋盘内
        if (mx <= bx && my <= by){
            dp[mx][my] = -1;
        }
        //将马能到达的位置置为 -1
        for (int i = 0; i <= bx; i++) {
            for (int j = 0; j <= by; j++) {
                if (mx != i && my != j && Math.abs(i - mx) + Math.abs(j - my) == 3) {
                    dp[i][j] = -1;
                }
            }
        }
        System.out.println(process(dp, bx, by));
    }

    public static long process(long[][] dp, int bx, int by) {
        //最后一列，无法到达右边，是特殊情况1
        for (int j = by; j >= 0; j--) {
            if (dp[bx][j] == -1) break;
            dp[bx][j] = 1;
        }
        //最后一行，无法到达下方，是特殊情况2
        for (int i = bx; i >= 0; i--) {
            if (dp[i][by] == -1) break;
            dp[i][by] = 1;
        }
        
        for (int j = by - 1; j >= 0; j--) {
            for (int i = bx - 1; i >= 0; i--) {
               // 已经置-1的地方直接跳过
                if (dp[i][j] == -1){
                    continue;
                }
                //右和下都是-1，置0
                if (dp[i + 1][j] == -1 && dp[i][j + 1] == -1) {
                    dp[i][j] = 0;
                    continue;
                }
                //仅下为-1
                if (dp[i + 1][j] == -1) {
                    dp[i][j] = dp[i][j + 1];
                    continue;
                }
                //仅右为-1
                if (dp[i][j + 1] == -1) {
                    dp[i][j] = dp[i + 1][j];
                    continue;
                }
                //右和下都不为-1
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }
}