洛谷 P1002 [NOIP2002 普及组] 过河卒

第一个dp（动态规划）题纪念一下

先尝试暴力写一个

递归，由于x与y只能增加，不存在回路。

#include<iostream>
using namespace std;
int a_x, a_y, h_x, h_y,sum=0;//a_x,a_y代表目标地点，h_x,h_y代表马的位置
long long map[21][21] = { 0 };//最后结果大，需要开long long
void dfs(int x,int y) {
    if (x == a_x && y == a_y) {//到达目标地点
        sum++;
        return;
    }
    if (x+1<=a_x&&map[x + 1][y]!=-1) dfs(x + 1, y);//访问x+1
    if (y+1<=a_y&&map[x][y + 1]!=-1) dfs(x, y + 1);//访问y+1
}
int main() {
    cin >> a_x >> a_y >> h_x >> h_y;
    int x_y[9][2] = { {0,0},{2,1},{1,2},{2,-1},{-1,2},{-2,1},{1,-2},{-2,-1},{-1,-2} };
    for (int i = 0; i < 9; i++)//标记马的控制区域
        map[h_x + x_y[i][0]][h_y+x_y[i][1]] = -1;
    dfs(0,0);
    cout<<sum<<endl;
    return 0;
} 

自然，这种方法中间会有两个点TLE。

不要问为啥不直接动态规划，问就是太菜，憋不出状态转移方程（悲）

进行动态规划

将map数组中的数字当成，在当前位置到目标位置的方法种数。

明显对于map数组中任意一个点(x,y)的值f(x,y)，都等于它的f(x+1,y)+f(x,y+1)，如果x+1,y+1小于等于20且不是马的控制点。

答案就在map数组的(0,0)处，根据这个性质，可以从目标位置开始填map数组，按照让x从大到小，y从大到小的顺序填充，直到填到(0,0)

#include<iostream>
using namespace std;
int a_x, a_y, h_x, h_y;
long long map[21][21] = { 0 };
int main() {
  cin >> a_x >> a_y >> h_x >> h_y;
  
  int x_y[9][2] = { {0,0},{2,1},{1,2},{2,-1},{-1,2},{-2,1},{1,-2},{-2,-1},{-1,-2} };
  for (int i = 0; i < 9; i++)//初始化map
    map[h_x + x_y[i][0]][h_y+x_y[i][1]] = -1;
  map[a_x][a_y] = 1;//目标点的值为1
  
  for(int j=0;j<=a_y;j++)//两层循环，访问的y值从大到小
  for (int i=0;a_x-i>=0;i++) {//访问的x值从大到小
    if (map[a_x-i][a_y-j]>=0){//防止修改马的控制点
      if (map[a_x + 1-i][a_y - j] > 0 && a_x + 1-i <= 20)
        map[a_x - i][a_y - j] += map[a_x-i + 1][a_y - j];//+=f(x+1,y)
      if (map[a_x-i][a_y + 1 - j] > 0 && a_y + 1 - j <= 20)
        map[a_x - i][a_y - j] += map[a_x-i][a_y + 1 - j];//+=f(x,y+1)
    }
  }
    cout << map[0][0] << endl;
  return 0;
}