将一个大问题分解成若干相互重叠的小问题，通过存储这些小问题的解以避免重复运算，提高效率。

可以使用DP的问题特征：

  • 重叠子问题：比如递归时，某些数据被重复计算多次；
  • 最优子结构：大问题的解可以通过解决小问题推导出来；
  • 无后效性：一旦一个状态被确定了，就不受之后决策的影响

举个例子：过河卒问题

题目：https://www.luogu.com.cn/problem/P1002

回溯算法结果

时间复杂度为O(2eX+eY)O(2^{eX + eY})，只能得60分。源代码如下：

import java.util.Scanner;
public class Main{
    public static int sum=0;
    public static void routeSelect(int x,int y,int hX,int hY,int eX,int eY){
        //System.out.println(x+" "+y);
        if(x==eX&&y==eY){ ++sum; return;}
        if (x > eX || y > eY) return;
        if( Math.pow(Math.abs((x+1)-hX),2) + Math.pow(Math.abs(y-hY),2) != 5 ){
            if((x+1)!=hX||y!=hY)    routeSelect(x+1,y,hX,hY,eX,eY);
        }

        if( Math.pow(Math.abs(x-hX),2) + Math.pow(Math.abs((y+1)-hY),2) != 5 ){
            if(x!=hX||(y+1)!=hY)    routeSelect(x,y+1,hX,hY,eX,eY);
        }
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int x=0,y=0,eX=scanner.nextInt(),eY=scanner.nextInt(),hX=scanner.nextInt(),hY=scanner.nextInt();
        //System.out.println(x+" "+y+" "+hX+" "+hY+" "+eX+" "+eY);
        routeSelect(x,y,hX,hY,eX,eY);
        System.out.println(sum);
    }
}

导致效率低下的原因：

  • 每一次递归都要重新计算马的控制点
  • 很多坐标被重复进入很多次

使用DP的改进思路：

  • 预先把马的控制点存入一个boolean型数组
  • 从起点开始，计算出每一个格子的所需路径，存入dp[x][y]
  • 最后计算路径数时，直接把左边格子和上边格子的路径数相加即可

具体实现

第一步：定义数组

long[][] dp;
boolean[][] isBad;

第二步：标记控制点

int[] dx = {0, -2, -1, 1, 2, 2, 1, -1, -2}; //水平间隔
int[] dy = {0, 1, 2, 2, 1, -1, -2, -2, -1}; //竖直间隔
for (int i = 0; i < 9; i++) {
    int curX = hX + dx[i];
    int curY = hY + dy[i];
    if (curX >= 0 && curX <= eX && curY >= 0 && curY <= eY) {
        isBad[curX][curY] = true; //标记坐标为控制点
    }
}

第三步：填表

起点位于(0,0)(0,0)，那么到达起点的路径为1种，即dp[0][0]=1

两层循环遍历棋盘：

dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j]=dp[i−1][j]+dp[i][j−1]

（如果 (i,j)(i,j) 是禁区，则 dp[i][j]=0）

最终代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 目标坐标 (eX, eY)，马的坐标 (hX, hY)
        int eX = sc.nextInt();
        int eY = sc.nextInt();
        int hX = sc.nextInt();
        int hY = sc.nextInt();

        // 初始化数组
        long[][] dp = new long[eX + 1][eY + 1];
        boolean[][] isBad = new boolean[eX + 1][eY + 1];

        // 标记马的控制点
        int[] dx = {0, -2, -1, 1, 2, 2, 1, -1, -2};
        int[] dy = {0, 1, 2, 2, 1, -1, -2, -2, -1};
        for (int i = 0; i < 9; i++) {
            int nx = hX + dx[i];
            int ny = hY + dy[i];
            if (nx >= 0 && nx <= eX && ny >= 0 && ny <= eY) {
                isBad[nx][ny] = true;
            }
        }

        // 递推计算
        for (int i = 0; i <= eX; i++) {
            for (int j = 0; j <= eY; j++) {
                if (isBad[i][j]) {
                    dp[i][j] = 0; // 如果是马的控制点，路径数为 0
                } else if (i == 0 && j == 0) {
                    dp[i][j] = 1; // 起点初始化
                } else {
                    // 到达当前点的路径 = 来自上方 + 来自左方
                    long fromTop = (i > 0) ? dp[i - 1][j] : 0;
                    long fromLeft = (j > 0) ? dp[i][j - 1] : 0;
                    dp[i][j] = fromTop + fromLeft;
                }
            }
        }

        System.out.println(dp[eX][eY]);
    }
}
Accepted