杨辉三角算法(leetcode第119题)

题目描述：

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。



 

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:

输入: rowIndex = 0
输出: [1]
示例 3:

输入: rowIndex = 1
输出: [1,1]
 

提示:

0 <= rowIndex <= 33

算法：

思路：

动态规划，一维数组，后值覆盖前值，从后遍历

代码实现：

/**
 * Note: The returned array must be malloced,
 *  assume caller calls free().
 */
//time:O(n^2)
# include<stdlib.h>
# include<string.h>
int* getRow(int rowIndex, int* returnSize) {
    *returnSize = rowIndex + 1;//返回第某行数组长度
    int* row = (int *)malloc(sizeof(int) * (*returnSize));//开辟数组
    memset(row, 0, sizeof(int) * (*returnSize));//初始化
    row[0] = 1;//初始值
    //一般动态规划，都可以从后遍历，防止越界
    for (int i = 1; i <= rowIndex; ++i) {//倒序避免j-1<0的问题
        for (int j = i; j > 0; --j) row[j] += row[j - 1];//动态规划
    }
    return row;
}