LeetCode第62题: 不同路径uniquePaths(C语

思路1：最容易想的思路就是递归了，结果也很容易想，超时了。。

int uniquePaths(int m, int n){
    int a[m + 1][n + 1];
    if(m < 1 || n < 1)
        return 0;
    else if(m == 1 || n == 1)
        return 1;

    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);

}

思路2:对于一个mxn的方格，比如对于位置第2行第2列的方格，可以从第1行第2列右移，也可以从第2行第1列下移，而对于位置第1列第2行的方格，只能从第1列第1行的位置下移，而不能从第0列第2行右移，因为越界了；同理，对于第2列第1行的位置，也只能从第1列第1行的位置右移，无法从第2列第0行下移，也是因为越界了。通过上述分析总结，将方格分成两种情况：1、对于第一列和第一行的所有方格，只有一种走法；2、对于其他行列的普通方格，有两种走法，可以用动态规划的思路解决。

int uniquePaths(int m, int n){
    int a[m + 1][n + 1];
    
    for(int i = 1; i <= m; i++){
        a[i][1] = 1;
    }
    for(int j = 1; j <= n; j++){
        a[1][j] = 1;
    }
    
    for(int i = 2; i <= m; i++){
        for(int j = 2; j <= n; j++){
            a[i][j] = a[i-1][j] + a[i][j-1];
        }
    }
    
    return a[m][n];
}

本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。
下一题：LeetCode第63题: 不同路径uniquePathsWithObstacles(C语言)