从棋盘左上角走到右下角有多少种走法

题目:

请编写一个函数（允许增加子函数），计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各 自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左 和往上走。
输入描述： 输入两个正整数
输出描述： 返回结果
示例1: 
输入
2 2
输出
6

---

解题思路:

看这个简单的4×4表格

我们发现想到达第一横行 和 第一竖列的每一个点的走法只有一种 所以我们在结点上都标上1 表示走到这里只有一种走法

然后我们再看(1,1)这一点 想走到这里我们可以从(0,1)走过去 也可以从(1,0)这个点走过去 所以有(1+1)两种走法

往后看我们不难看出 想走到某一点的走法等于其左边第一个点的走法数加上其上面第一个点的走法数

如上图(1+1)=2 , (1+2)=3 ,(1+3)=4 ,(1+4)=5  分析到这里我们的代码呼之而出

---

代码展示:

#include <iostream>
#include <vector>
using namespace std;

int Total_ways(int n, int m) {
		int ways = 0;
		vector<vector<int>> vi;
		vi.resize(n+1);
		for (int i = 0;i <=n;i++) {
			vi[i].resize(m+1,1);
		}
		for (int i = 0;i <= n;i++) {
			for (int j = 0;j <= m;j++) {
				if (j - 1 >= 0 && i - 1 >= 0) {
					vi[i][j] = vi[i][j - 1] + vi[i - 1][j];
				}
			}
		}
		ways = vi[n][m];
		return ways;
	}

	int main() {
		int a, b;
		cin >> a >> b;
		cout << Total_ways(a, b) << endl;
		system("pause");
		return 0;
	}

---

部分代码分析:

上述代码最需要注意的是 在resize的时候记得要比行数和列数多一个 即 resize(n+1) resize(m+1)

在resize的时候记得将每一个点的数初始化为1 这是为了将第一列和第一行的节点置1