leetcode-62.不同路径

1. 题目

2. 解答

dp[i][j]表示机器人位于第i，j位置的时候，有多少路径

1. 如果i = 0，dp[i][j] = 1;
2. 如果j = 0，dp[i][j] = 1;
3. 其他情况dp[i][j] = dp[i-1][j] + dp[i][j - 1]

#include 

int solve(int m, int n)
{
    int dp[m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

    return dp[m -1][n -1];
}

int main()
{
    int m, n;
    scanf("%d %d", &m, &n);

    int result = solve(m, n);

    printf("result:%d\n", result);
}
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

运行：

G3-3579:~/data/source/leetcode$ gcc 62differrentpath.c 
G3-3579:~/data/source/leetcode$ ./a.out 
3 7
result:28
G3-3579:~/data/source/leetcode$ ./a.out 
3 2
result:3
G3-3579:~/data/source/leetcode$ ./a.out 
7 3
result:28
G3-3579:~/data/source/leetcode$ ./a.out 
3 3
result:6
1
2
3
4
5
6
7
8
9
10
11
12
13