62. 不同路径

62. 不同路径
    一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28
示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
   示例 3：

输入：m = 7, n = 3
输出：28
示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

// 使用动态规划进行解决
// 1、确定dp数组的含义
// dp[i][j] 表示到达位置（i,j）， 一共有多少种路径
// 2、确定递推公式
// 1)如果当前位置是从它的上方位置移动过来了，那么dp[i][j] = dp[i - 1][j];
// 2)如果当前位置是从它的左边移动过来的，那么dp[i][j] = dp[i][j - 1];
// 综上所述：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
// 3、确定初始化
// 初始位置都是从(0,0)开始，那么到达该位置有一种方法，dp[0][0] = 1;
// 对于边缘位置，如i=0，j != 0 的位置，dp[0][j] = 1;
// 4、确定dp递推顺序
// 这个dp是二维数组，同时两个变化步骤没有先后顺序，所以按照从左到右，然后从上到下的顺序进行遍历
// 5、确定结果位置
// dp[m-1][n-1] 即为最终结果位置
// 6、进行举例验证
// m = 3, n = 7
// 1 1 1 1 1 1 1 
// 1 2 3 4 5 6 7
// 1 3 6 10 15 21 28
// 所以最后结果是 28 种

int uniquePaths(int m, int n){

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

    for (i = 0; i < m; i++) {
        dp[i][0] = 1;
    }

    for (i = 0; i < n; i++) {
        dp[0][i] = 1;
    }


    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    int ans = dp[m - 1][n - 1];

    for (i = 0; i < m; i++) {
        free(dp[i]);
        dp[i] = NULL;
    }
    free(dp);
    dp = NULL;

    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55