7-3 营养快线马上就到（百度之星校赛题目）
分数 30
作者 HZU-ACM
单位 惠州学院
题目描述:
故事要从某一天机房训练赛说起 O_O
某段时间，fuzhiji沉迷于喝营养快线，不喝营养快线比赛的时候就疯狂”表演“（会做的都写错）， 来自uzh的某届最强ACMer轩哥为了让fuzhiji在比赛中发挥出全部的实力，决定顺路给他带一瓶营养快线。
机房附近只有一个小卖部，在二维平面上用 (1,1) 表示。
轩哥从小卖部 (1,1) 出发，他需要把营养快线带到机房 (n,n) 给fuzhij。
假设轩哥在 (x,y) 点，那么轩哥下一步可以走到 (x+1,y) 或 (x,y+1) 的位置。
由于校园很大，所以轩哥行走路线难以捉摸，但是当天是四六级的考试，有些考点被封锁的，禁止通行，比如 (sx,sy) 点当作了考点，那么轩哥不能经过 (sx,sy) 这个点。
由于不能出校，所以轩哥只能在 (x,y)，1<=x<=n,1<=y<=n 这些点范围内活动，校园可以看成一个 n * n 的矩形。
fuzhiji想知道轩哥从小卖部到机房有几种不同的行走路线，要是换在平时，他可以轻松写个程序解决，但是因为今天没喝营养快线，代码老写错，于是他找到了一个代码高手帮忙------没错，就是你。
当两条线路：
线路A：(1,1)->(x_1,y_1)->(x_2,y_2)->…->(x_k,y_k)->…->(n,n)
线路B：(1,1)->(x_1,y_1)->(x_2,y_2)->…->(x_k,y_k)->…->(n,n)
若存在某个数 k 使得线路A的 (x_k,y_k) 和线路 B 的 (x_k,y_k)不是同一个点，那么 A 和 B 就是两条不同的路线。
输入格式:
第一行给出 n m ------ n 表示学校所表示的矩形大小的范围，m 表示四六级考点的个数
接下来 m ⾏，每⾏给⼀个考点 (x,y) 且 1<=x,y<=n
保证 m 个 (x,y) 中不会出现重复点
保证⼩卖部 (1,1) 和机房 (n,n) 都不是考点
输出格式:
输出⼀个数字，表⽰轩哥有⼏种⾛法，如果没有可⾏路线，输出 0，由于路径数量可能很大，所以输出路径数量对 1e9+7 取模的结果。（例如有ans条路径，那么输出ans%1000000007）。
输入样例1:
2 1
1 2
输出样例1:
1
输入样例2:
2 2
1 2
2 1
输出样例2:
0
输入样例3:
2 0
输出样例3:
2
输出样例3:
对于35%的数据：
1<=n<=5
1<=m<=5
对于另外20%的数据：
1<=n<=2000
m=0
对于另外45%数据：
1<=n<=2000
0<=m<=n*n-2
对于全部样例，都有
1<=x,y<=n
代码长度限制
16 KB
时间限制
1000 ms
内存限制
512 MB
暴力 - 记忆化搜索 - dp
#include<iostream>
using namespace std;
const int N = 2e3 + 10, A = 1e9 + 7;
int n, m;
bool st[N][N];//标记
int num;
int dx[2] = { 1, 0 }, dy[2] = { 0, 1 };
//dfs暴力搜索（维护全局变量）
//void dfs(int a, int b)
//{
// if (a == n && b == n)
// {
// num = (num + 1) % A;
// return;
// }
//
// for (int i = 0; i < 2; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 1 && x <= n && y >= 1 && y <= n && !st[x][y])
// {
// st[x][y] = 1;
// dfs(x, y);
// st[x][y] = 0;
// }
// }
//}
//带返回的dfs
//int dfs(int a, int b)//返回从(a, b）出发到（n, n）的路径个数
//{
// if (a == n && b == n)
// {
// return 1;//根据返回值进行判断
// }
//
// int sum = 0;
// for (int i = 0; i < 2; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 1 && x <= n && y >= 1 && y <= n && !st[x][y])
// {
// //注意此时无需再进行回溯
// sum = (sum + dfs(x, y)) % A;
// }
// }
//
// return sum;
//}
int f[N][N];
////记忆化搜索
//int dfs(int a, int b)//返回从(a, b）出发到（n, n）的路径个数
//{
// if (f[a][b]) return f[a][b];
// if (a == n && b == n)
// {
// return 1;//根据返回值进行判断
// }
//
// int sum = 0;
// for (int i = 0; i < 2; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 1 && x <= n && y >= 1 && y <= n && !st[x][y])
// {
// st[x][y] = 1;
// sum = (sum + dfs(x, y)) % A;
// st[x][y] = 0;
// }
// }
//
// f[a][b] = sum;
// return sum;
//}
int main()
{
scanf("%d%d", &n, &m);
while (m--)
{
int a, b;
scanf("%d%d", &a, &b);
st[a][b] = 1;//标记为四六级考点
}
//dfs(1, 1);
//cout << dfs(1, 1) << endl;
//dfs(1, 1);
//cout << f[1][1] << endl;
//根据记忆化搜索 - dp
//状态：（i， j）所有从（i，j）-(n,n)的所有路径
//属性：f[][] 个数
//状态划分：关注最后一个不同点， 要么从下面到（i，j），要么从右侧到（i，j）
//初始化
f[n][n] = 1;
for (int i = n; i >= 1; i--)
{
for (int j = n; j >= 1; j--)
{
for (int k = 0; k < 2; k++)
{
int x = i + dx[k], y = j + dy[k];
if (x >= 1 && x <= n && y >= 1 && y <= n && !st[x][y])
{
f[i][j] = (f[i][j] + f[x][y]) % A;
//f[i + 1][j], f[i][j + 1]
}
}
}
}
//空间优化 （x 此处的初始化，无法再优化的情况下正确对 f[n][n]赋值， 并不知道此时f[n] 是 哪个i）
//f[n] = 1;
//for (int i = n; i >= 1; i--)
//{
// for (int j = 1; j <= n; j++)//注意顺序
// {
// for (int k = 0; k < 2; k++)
// {
// int x = i + dx[k], y = j + dy[k];
// if (x >= 1 && x <= n && y >= 1 && y <= n && !st[x][y])
// {
// f[j] = (f[j] + f[y]) % A;
// //f[i + 1][j], f[i][j + 1]
// }
// }
// }
//}
//cout << f[1] << endl;
return 0;
}
理解：暴力dfs搜索全部可行解（维护全局变量）的同时需要 回溯操作，但是优化成记忆化搜索或dp的时候，无需再进行 回溯操作， 得益于返回值或状态的定义
