力扣路径问题个人思路不解

Question

int a=0,b=0,c=0,d=0;
int jisuan(int a,int b,int m,int n)
{
    if(a<m) {c=jisuan(a+1,b,m,n);}else{c=0;}
    if(b<n) {d=jisuan(a,b+1,m,n);}else{d=0;}
    if(a==m&&b==n)
    {
        return 1;
    }
    else{
        return c+d;
    }
    
}
int uniquePaths(int m, int n) {
    return jisuan(0,0,m,n);
}

Answer 1

只是递归的话很简单

int uniquePaths(int m, int n) {
    if(m == 1 || n == 1)
        return 1;
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}

但是遇见mn比较大的用例会超时，所以再加上记忆化搜索

int inPos(int x, int y, int **pos)
{
    if(pos[x][y])
    {
        return pos[x][y];
    }

    if(x == 0 || y == 0)
        return 1;
    pos[x][y] = inPos(x - 1, y, pos) + inPos(x, y - 1, pos);

    return pos[x][y];
}

int uniquePaths(int m, int n) {
    int** pos = (int**)malloc((m) * sizeof(int*));
    for (int i = 0; i < m; i++) {
        pos[i] = (int*)malloc((n) * sizeof(int));
        memset(pos[i], 0, (n) * sizeof(int));
    }

    return inPos(m - 1, n - 1, pos); 
}

当然，这里没有回收pos数组，单纯的懒得写而已