海宁网站建设公司推荐,wordpress主题开发网站,哈尔滨市工程建设监理有限公司,阿里云 个人网站给定一个非负整数 numRows#xff0c;生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中#xff0c;每个数是它左上方和右上方的数的和。
思路一#xff1a;动态规划
int** generate(int numRows, int* returnSize, int** returnColumnSizes){int **returnnum(int **)…给定一个非负整数 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(i0;inumRows;i){returnnum[i](int *)malloc(sizeof(int)*(i1));(*returnColumnSizes)[i]i1;returnnum[i][0]1;returnnum[i][i]1;if(i2){for(j1;ji;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]即可解决
