计算n x m的棋盘格子, 沿着各自边缘线从左上角走到右下角，总共有多少种走法. 要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

た入场券 2023-06-13 08:56 32阅读 0赞

语言C++

> **题目 : **\[编程题\]201301 JAVA 题目2-3级
> 
> **题目描述 : **
> 
> 请编写一个函数（允许增加子函数），计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
> 
>  
> 
> **输入描述:**
> 
> 输入两个正整数
> 
> **输出描述:**
> 
> 返回结果
> 
> 示例:
> 
>         输入
> 
>     2
>     2
> 
>         输出
> 
>     6
> 
> [OJ链接：https://www.nowcoder.com/questionTerminal/e2a22f0305eb4f2f9846e7d644dba09b][OJ_https_www.nowcoder.com_questionTerminal_e2a22f0305eb4f2f9846e7d644dba09b]  
> 来源：牛客网

> 先吐槽一下, 这题目名字是个什么鬼.. 还有就是, 需要循环输入测试用例  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]
> 
> 已经好几次做题时怎么调试都死活通不过, 就是死在这个循环输入测试用例上面, 可气的是, 题目里根本不说啊, 有的题不用写循环就能通过, 有的必须写, 真是头都大了ヽ(\#\`Д´)ﾉ┌┛〃
> 
> **分析 :**
> 
> 两种思路, 动态规划或者递归, 要注意的是, 路径走的是格子边缘西安, 并不是格子
> 
> **1. 动态规划**
> 
> 这道题的动态规划解法较为简单, 利用的是子问题之间不独立,举个栗子, 在本题中, 即 3 x 4棋盘的走法数与 2 x 4 有
> 
> 关. 本题可以根据前两个阶段有几种走法来导出本阶段有几种走法. 干想是不好想的, 既然题中有棋盘, 那我们就找一个, 由少
> 
> 到多的找出规律, 写出状态转移方程
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]
> 
> 通过棋盘由小到多, 我们隐约发现, 从左上角到右下角的走法与左边的格子, 和上边的格子有关, 如果将格子看成一个二维数组的话, 就a\[ i \]\[ j \] = a\[ i-1\]\[ j \] + a\[ i \]\[ j-1\]的关系,  为了确认是不是, 我们多画几个看一看
> 
> ![20191115163920359.png][]                   ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2][]
> 
> 我们已经能确认状态转移为a\[ i \]\[ j \] = a\[ i-1\]\[ j \] + a\[ i \]\[ j-1\], 但起始第一行和第一列却只有前一个状态, 可以发现, 第一行或
> 
> 第一列往后都是加一, 我们为了更好的满足状态转移方程, 可以给现有的棋盘加上起始行和起始列, 如下
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3][]
> 
> 可以看到这样一张表, 我们最该想到二维数组了, 现在就简化成了利用初始状态和状态方程填表的问题, 表的右下角的元素值
> 
> 就是我们要的结果代码实现如下:

#include<iostream>
    #include<vector>
    using namespace std;
    class Solution {
    public:
        long long fun(int n, int m) {
            vector<vector<long long> > v;
            v.resize(n + 1, vector<long long>(m + 1));
            for (int i = 1; i < m + 1; ++i) {
                v[0][i] = 1;
            }
            for (int i = 1; i < n + 1; ++i) {
                v[i][0] = 1;
            }
            for (int i = 1; i < n + 1; ++i) {
                for (int j = 1; j < m + 1; ++j) {
                    v[i][j] = v[i - 1][j] + v[i][j - 1];//状态转移方程
                }
            }
            return v[n][m];
        }
    };
    int main() {
        int n, m;
        Solution f;
        while (cin >> n >> m) {
            cout << f.fun(n, m) << endl;
        }
        system("pause");
        return 0;
    }

这种解法还可以简化一下, 用一维数组来做, 思路也是一样的不过每次填的数字会覆盖掉原来的值, 如下 :

#include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    class Solution {
    public:
    	long long fun(int n, int m) {
    		vector<long long> v;
    		v.resize(m + 1, 1);
    		for (int i = 1; i < n + 1; ++i) {
    			for (int j = 1; j < m + 1; ++j) {
    				v[j] += v[j - 1];
    			}
    		}
    		return v[m];
    	}
    };
    int main() {
    	int n, m;
    	Solution f;
    	while (cin >> n >> m) {
    		cout << f.fun(n, m) << endl;
    	}
    	system("pause");
    	return 0;
    }

> **2. 递归**
> 
> 递归也一样, 需要先知道其状态转移方程,  也就是f( i, j ) = f( i - 1, j ) + f( i, j - 1 ), 同样, 和递归一样也需要注意边界问题, 当棋
> 
> 盘的行或者列(即这里的i, j)有一个为0时, 即左上角和右下角重合时, 只有一种走法, 这就是递归结束条件
> 
>   
> PS: 递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实
> 
> 现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优
> 
> 势，这也是动态规划算法的核心之处。
> 
> 比如输入20, 20, 动规可以秒出, 递归嘛, 算了好长时间都没算出来.....
> 
> 来祭出代码

#include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    class Solution {
    public:
    	long long fun(int n, int m) {
    		if (n == 0 || m == 0) {
    			return 1;
    		}
    		return fun(n - 1, m) + fun(n, m - 1);
    	}
    };
    int main() {
    	int n, m;
    	Solution f;
    	while (cin >> n >> m) {
    		cout << f.fun(n, m) << endl;
    	}
    	system("pause");
    	return 0;
    }

[OJ_https_www.nowcoder.com_questionTerminal_e2a22f0305eb4f2f9846e7d644dba09b]: https://www.nowcoder.com/questionTerminal/e2a22f0305eb4f2f9846e7d644dba09b
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191115094946399.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191115163332775.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[20191115163920359.png]: https://img-blog.csdnimg.cn/20191115163920359.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191115163934829.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191115170545548.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70