HJ91 题解 | #走方格的方案数#

题意分析

• 一个很经典的题目，给出一个二维矩阵，从左上角走到右下角，每次只能往右走或者往下走，问我们有多少种走的方案？

思路分析

解法一 动态规划

• 我们发现，假设我们某一个时刻走到了位置$(i,j)(i,j)$,那么，我们如何求到达这个位置的情况的数目呢？

• 所以我们可以很容易得到状态转移方程,$dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]=dp[i-1][j]+dp[i][j-1]$。

• 代码如下

  • 二维循环，先进行行的遍历，再进行列的遍历，更新每个位置的状态。时间复杂度为$O(nm)O(nm)$
  • 需要存储每个位置的状态，空间复杂度为$O(nm)O(nm)$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=20;
ll dp[N][N];
int main(){
    int n,m;
    while(cin>>n>>m){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                // 如果是初始的位置
                if(i==0&j==0){
                    dp[i][j]=1;
                    continue;
                }
                // 如果是第一行，那么直接从左边转移过来
                if(i==0){
                    dp[i][j]=dp[i][j-1];
                    continue;
                }
                // 如果是第一列，那么直接从上面转移过来
                if(j==0){
                    dp[i][j]=dp[i-1][j];
                    continue;
                }
                // 否则，可以从上面和左边转移过来
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        cout<<dp[n][m]<<endl;
    }
}

解法二 数学排列组合

• 我们发现，我们走的步数是固定的，对于每走一步，我们只能有两个选择，要么向右边，要么向下边，而且，我们发现，我们向右和向下的步数是固定的，所以我们就可以将题目转化为在一共n+m步中，选择其中的n步往下走的情况的数目，或者说选择m步往右走的情况的数目。这样，就是一个很显然的数学排列组合题目了。

• 代码如下

  • 最坏的循环的次数为n+m,所以总的时间复杂度为$O(n+m)O(n+m)$
  • 只开了少数几个变量，空间复杂度为$O(1)O(1)$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int main(){
    int n,m;
    while(cin>>n>>m){
        ll up=1,down=1;
        // 计算(m+n)!/m!
        for(int i=n+m;i>m;i--){
            up=up*i;
        }
        // 计算n!
        for(int i=n;i;i--){
            down=down*i;
        }

        ll ans=up/down;
        cout<<ans<<endl;
    }
}