关于#矩阵#的问题，如何解决？

题目描述
给定一个n*m的矩阵，问从左上角的交叉点走到右下角的交叉点有多少条不同的路径（同一路径不允许重复走，也不允许往回走）
输入格式
一行两个正整数 n,m
输出格式
路径数目 t
样例
样例输入：
6 4
样例输出：
210
数据范围与提示

你去leetcode看看，有很多算法题，你这个就是原题

我要题解

#include<cstdio>
#include<ctype.h>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
inline ll read();

struct big_num
{
    int a[1010];
    int len;
    inline void big_num_memset()
    {
        memset(a,0,sizeof(a));
        a[1]=1;
        len=1;
    }
};

big_num operator * (const big_num &a,const int b)
{
    int L=a.len,jw=0;
    big_num c=a;
    for (register int i=1;i<=L;++i)
    {
        c.a[i]=c.a[i]*b+jw;
        jw=c.a[i]/10;
        c.a[i]%=10;
    }
    ++L;
    c.a[L]=jw;
    while (c.a[L]!=0)
        c.a[L+1]+=c.a[L]/10,c.a[L]%=10,++L;
    --L;
    c.len=L;
    return c;
}

big_num operator / (const big_num &a,const int b)
{
    big_num c=a;
    int tw=0,L=a.len;
    for (register int i=L;i>=1;--i)
    {
        int k=(tw*10+c.a[i])/b;
        tw=(tw*10+c.a[i])%b;
        c.a[i]=k;
    }
    while (c.a[L]==0) --L;
    c.len=L;
    return c;
}

inline big_num C(ll n,ll m)//C(n,m)=m!/(n!(m-n)!)
{
    big_num res;
    res.big_num_memset();
    if (n==0) return res;
    for (register int i=n+1;i<=m;++i)
        res=res*i/(i-n);
    return res;
}

inline void print(big_num a)
{
    if (a.len>17)
    {
        for (register int i=a.len;i>=a.len-16;--i)
            cout<<a.a[i];
        for (register int i=a.len-17;i>=1;--i)
            cout<<"0"; 
    }
    else
        for (register int i=a.len;i>=1;--i)
            cout<<a.a[i];
}

ll n,m;

int main()
{
    n=read(),m=read();
    print(C(n,m+n));
    return 0;
}

inline ll read()
{
    ll x=0,f=0;
    char c=getchar();
    while (!isdigit(c))
        f|=c=='-',c=getchar();
    while (isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

这个对吗？

搜索与回溯

（1）暴力法（回溯法）
使用递归的方法来做，代码如下：

void FindUniquePaths(int m, int n, int i, int j, int &sum)
{
    if (i == m || j == n)
    {
        return ;
    }
    if (i == m - 1 && j == n - 1)
    {
        sum ++;
    }
    else
    {
        FindUniquePaths(m, n, i + 1, j, sum);
        FindUniquePaths(m, n, i, j + 1, sum);
    }
}
 
int UniquePaths(int m, int n) {
    int sum = 0;
    FindUniquePaths(m, n, 0, 0, sum);
    return sum;
}

（2）动态规划
使用一个 m x n 的数组 path，其中 path[ i ] [ j ] 表示从 [ 0 ] [ 0 ] 点到 [ i ] [ j ] 的路径数，则有 path[ 0 ] [ 0 ] = 1, path[ i ] [ j ] = path[ i - 1 ] [ j ] + path[ i ] [ j - 1 ]。代码如下：

int UniquePaths(int m, int n) {
    vector<vector<int>> path(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int left = 0;
            if (j > 0)
            {
                left = path[i][j - 1];
            }
            int up = 0;
            if (i > 0)
            {
                up = path[i - 1][j];
            }
            if (i == 0 && j == 0)
            {
                path[i][j] = 1;
            }
            else
            {
                path[i][j] = left + up;
            }     
        }
    }
    return path[m - 1][n - 1];
}