DP-N*M棋盘走法

DP 计数类问题的典型套路：最优、最大、最小、最长、计数。

题目：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，无需额外处理。