动态规划-杨辉三角（leetcode）

1. 题目

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:

输入: numRows = 1
输出: [[1]]

2. 思路与实现

当n=1时：f(1) = 1;
当n=2时：f(2) = 1,1;
当n=3时：f(3) = 1,f(2.1)+f(2.2),1; 有一个数字需要计算
当n=4时：f(4) = 1, f(3.1) +f(3.2), f(3.2) + f(3.3), 1; 有两个数字需要计算
所以当n>2的时候，有f(n) = n-2个数字需要计算；

实现：

#include 
#include 

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

    int **map;
    int *num;

    map = malloc(sizeof(int *) * n);
    num = malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++) {
        map[i] = malloc(sizeof(int) * (i + 1));
        num[i] = i + 1;
        for (int j = 0; j < i + 1; j++) {
            if (i == 0 || i == 1 || j == 0 || j == i) {
                map[i][j] = 1;
            } else if (i > 1) {
                map[i][j] = map[i - 1][j -1] + map[i - 1][j];
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < num[i]; j ++) {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }

}
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

结果：

./a.out 
5
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1
2
3
4
5
6
7