套路：计数问题 ， 最优，最大，最小，最长，计数

N*M的棋盘上，小兵要从左下角走到右上角，只能向上或者向右走， 问有多少种走法

先的得出递归暴力解法

int f(int x, int y){	if (x <= 0 || y <= 0)return 0; //某一个方向为0 那么已经到达了目标点	if (x == 1 || y == 1)return 1;某一个方向为1 那么到达目标点只有一种走法	return f(x - 1, y)+f(x, y - 1);//左或者右 有多少走法}

然后转换为DP

int arr[10][10];	memset(arr, 0, 4*10*10);	for (int i = 0; i <= 5; i++)	{		arr[1][i] = 1;//根据递归式 写出初始状态		arr[i][1] = 1;	}	for (int x = 2; x <= 6; x++)	{		for (int y = 2; y <= 6; y++)		{			arr[x][y] = arr[x - 1][y] + arr[x][y-1];//递推		}	}	cout << arr[6][6] << endl;

如果不允许某几格不能走，那么可以吧该格置为0表示该状态下没有，在递归式中表示为判断n m是否是可走的，不可走返回0，转换到DP其实就变成了初始值为0