一道简单题引发的思考

☘前言☘

其实好久都不写算法相关的题目了，最近某群友问了一道简单题，但是一时没想起来，后来深入思考了一下进行一下记录。

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min

---

---

题目描述

在NxM的方格中，以左上角格子为起点，右下角格子为终点，每次只能向下走或者向右走，请问一共有多少种不同的走法给定两个正整数int n,int m，请返回走法数目。
注：空间复杂度最好为O(n)
(是一道面试题，没找到出处。)

---

解法一

思路

第一反应就是动态规划，但是要求空间复杂度为O(n)不能使用矩阵了，但是看规律，每个格子的路径数目等于上面一个和左面一个的路径和，如果做压缩为一维的话，可以看作，每个都是前一个和当前格子的和。

代码

#include
#include

int count(int m, int n){
    int tmp[n];
    memset(tmp,0,sizeof(tmp));
    for(int i = 0;i < n;++i)    tmp[i] = 1;
    for(int i = 1;i < m;++i)
        for(int j = 1;j < n;++j)
            tmp[j] += tmp[j-1];
    return tmp[n-1];
}

int main(){
    int m,n;
    scanf("%d %d",&m,&n);
    printf("%d\n",count(m,n));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

大概就是上面的样子。

---

解法二

思路

这是个美丽的意外，我以为这道题是要求时间复杂度为O(n)，这个事就复杂起来了，我第一反应是可重复排列组合数，但是没那么复杂，其实就是要走到右下角一定要走$m-1+n-1$步，其中有$n-1$步是要向右走的，那么按照排列组合的方式就是$\left(\genfrac{}{}{0ex}{}{n-1}{m+n-2}\right)$，如果按照这个公式计算的话就是$\frac{(m+n-2)...(m)}{(n-1)!}$，
复杂度就可以做到O(n)，唯一的问题是可能超范围，所以要开大点用longlong。

代码

#include
#include
using namespace std;

int count(int m, int n){
    long long ans = 1;
    for(int i = m;i < m+n-1;i++)
        ans *= i;
    for(int i = n - 1;i;i--)
        ans /= i;
    return ans;
}

int main(){
    int m,n;
    while(cin>>m>>n)
        cout<<count(m,n)<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

后记

今天就到这里了，这个系列不定时更新，主要看我有没有遇到我赶兴趣的0.0