过河卒（洛谷P1002题解，Java语言描述）

题目要求

P1002题目链接

分析

这个题分类是DP，动态规划~~ 用搜索解的话会超时…… 具体的规律见下文……

思路讲解的话可以说递推啊，动归啊，但其实我这种弱鸡就不是很能入目三分的理解了诶……

另外，这个题最后说了，结果可能很大，也就是说至少int不够，我终于学会不用int了，开了一个long的二维数组表示棋盘，大小的话多开了点，也不敢多开（MLE），生活不易啊~~

核心规律

每个数都等于它上面左边的数的和…… a[i][j]=a[i-1][j]+a[i][j-1] 用这个就可以解出来了……

简便解法——AC代码（Java语言描述）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long[][] chessBoard = new long[50][50];
        short y2 = scanner.nextShort(), x2 = scanner.nextShort(), y1 = scanner.nextShort(), x1 = scanner.nextShort();
        //隔出两格，当要把马可跳到的地方掷成0时不会出错
        y2 += 2;
        x2 += 2;
        y1 += 2;
        x1 += 2;
        for(int i = 2; i