套路：计数问题 ， 最优，最大，最小，最长，计数
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);//左或者右 有多少走法
}- 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);//左或者右 有多少走法
- }
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;
- 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;
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