🎈 原创

题目描述

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

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

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

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

输入输出样例

输入 #1

6 6 3 3

输出 #1

6

说明/提示

对于 100%100% 的数据，1≤n,m≤201≤n,m≤20，0≤0≤ 马的坐标 ≤20≤20。

【题目来源】

NOIP 2002 普及组第四题

---

这篇笔记纪念我第一次写出动态规划 :)

题目的意思很明确，就是找出从（0， 0）到（n， m）的路径的数。第一次写的时候用了DFS，结果TLE了，看了题解后知道要用动态规划，所以自己试着写了一下。

#include <iostream>
#include <algorithm>
using namespace std;

int X[9] = {-2, -1, 1, 2, 2, 1, -1, -2, 0};
int Y[9] = {1, 2, 2, 1, -1, -2, -2, -1, 0};
long long int dp[30][30] = {0};	//不用long long会WA两个点
int endX, endY, horseX, horseY;
int cnt = 0;

int main(int argc, const char * argv[])
{
    cin >> endX >> endY >> horseX >> horseY;
    dp[0][1] = 1;
    for(int i = 1; i <= endX + 1; i++)
        for(int j = 1; j <= endY + 1; j++)
        {
            bool flag = true;
            for(int k = 0; k < 9; k++)
                if(i == horseX + X[k] + 1 && j == horseY + Y[k] + 1)
                {
                    flag = false;
                    break;
                }
            if(flag)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            else
                dp[i][j] = 0;
        }

    cout << dp[endX + 1][endY + 1] << endl;

//    for (int i = 0; i <= endX + 1; i++) {
//        for (int j = 0; j <= endY + 1; j++) {
//            cout << dp[i][j] << " ";
//        }
//        cout << endl;
//    }

    return 0;
}

把起始点从（0， 0）设为（1， 1），相当于把矩阵平移了一下。

dp表示从起点到i, j的走法有几种。

刚开始提交的时候WA了两个点，把DP数组改成long long才AC，可见结果的数据值有多大。

---

空间优化

#include <iostream>
#include <algorithm>
using namespace std;

int X[9] = {-2, -1, 1, 2, 2, 1, -1, -2, 0};
int Y[9] = {1, 2, 2, 1, -1, -2, -2, -1, 0};
long long int dp[30] = {0};
int endX, endY, horseX, horseY;
int cnt = 0;

int main(int argc, const char * argv[])
{
    cin >> endX >> endY >> horseX >> horseY;
    dp[1] = 1;
    for(int i = 1; i <= endX + 1; i++)
        for(int j = 1; j <= endY + 1; j++)
        {
            bool flag = true;
            for(int k = 0; k < 9; k++)
                if(i == horseX + X[k] + 1 && j == horseY + Y[k] + 1)
                {
                    flag = false;
                    break;
                }
            if(flag)
                dp[j] += dp[j - 1];
            else
                dp[j] = 0;
        }
    
    cout << dp[endY + 1] << endl;
    



    return 0;
}

由于状态转移的时候需要一个dp[i - 1][j]来记录从上边走过来的情况，所以需要第一维，但是这一维可以用滚动数组优化。

dp[i] = dp[i] + dp[i - 1]可以用来优化，dp[i - 1]就是前面的dp[i][j - 1]表示从左边走过来的情况。由于这个数组是不断被更新的，所以当要去更新dp[i]时，dp[i]中存储的就是上一个状态，即dp[i - 1][j]。这样二维数组就可以被优化成一维的了。

还要注意的是dp数组的初始化问题。dp[0]应该被初始化成0，表示边界，就是没有办法从当前位置的左边走过来，而dp[1]才表示起点，设为1。