62. 不同路径

 

 

---

 动态规划

class Solution {
    

public:
    int uniquePaths(int m, int n) {

        if(m==0||n==0)return 1;
        if(m==0&&n==0)return 0;
        //用二维数组存储到达某点的路径数
        //初始化为1，因为第一行，第一列默认就是1，这样省区赋值了
        vector<vector<int>>res(m,vector<int>(n,1));
        //从res[1][1]开始考虑
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
                //当前值为左边，和上边的和
                res[i][j]=res[i][j-1]+res[i-1][j];
        }   
        return res[m-1][n-1];
    }
};

---

 回溯法，超时，

class Solution {
    
    void helper(int m, int n,int &res,int x,int y)
    {
        if(x==m&&y==n)
        {
            res++;
            return;
        }
        for(int i=0;i<2;i++)
        {
            if(i==0&&y+1<=n)
            {
                helper(m,n,res,x,y+1);
            }
            else if(i==1&&x+1<=m)
            {
                helper(m,n,res,x+1,y);
            } 
        }
    }
public:
    int uniquePaths(int m, int n) {

        if(m==0||n==0)return 1;
        if(m==0&&n==0)return 0;
        //表示有多少条路径
        //如果是定义的全局变量或者静态变量,未初始化的话就是0.如果是局部变量,那就是以前残留在堆栈里的随机值
        int res=0;
        helper(m,n,res,1,1);
        return res;
    }
};