leetcode做题笔记118. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

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

思路一：动态规划

int** generate(int numRows, int* returnSize, int** returnColumnSizes){int **returnnum=(int **)malloc(sizeof(int *)*numRows);*returnSize = numRows;*returnColumnSizes = malloc(sizeof(int) * numRows);int i,j;for(i=0;i<numRows;i++){returnnum[i]=(int *)malloc(sizeof(int)*(i+1));(*returnColumnSizes)[i]=i+1;returnnum[i][0]=1;returnnum[i][i]=1;if(i>=2){for(j=1;j<i;j++){returnnum[i][j]=returnnum[i-1][j-1]+returnnum[i-1][j];}}}return returnnum;
}

分析：

本题要求杨辉三角，每个数为上一行相同位置和前一位数之和，可用循环将每个数利用上一行计算出来，最后输出dp,即returnnum

总结：

本题考察动态规划的应用，找到状态方程dp[i][j] = dp[i-1][j-1]+dp[i-1][j]即可解决