动态规划攻略之：杨辉三角

动态规划攻略之：杨辉三角

题目

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

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

示例1：

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

示例2：

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

解题思路

根据题意可知，杨辉三角具有以下的特性：

每行数字左右对称，由 1 开始逐渐变大再变小，并最终回到 1。每个数字等于上一行的左右俩个数字之和，即第 n 行的第 i 个数等于第 n-1 行的第 i-1 个数和第 i 个数之和。

由此，我们可以一行一行地计算杨辉三角。每当我们计算出第 i 行的值，我们就可以在线性时间复杂度内计算出第 i+1 行的值。

代码实现

class Solution { public List> generate(int { List> nums = new ArrayList>(); for (int i = 0; i < numRows; i++) { List row = new ArrayList(); for (int j = 0; j <= i; j++){ if (j == 0 || j == i) { row.add(1); } else { row.add(nums.get(i-1).get(j-1) + nums.get(i-1).get(j)); } } nums.add(row); } return

最后

时间复杂度：O(n2)，n 为行数； 空间复杂度：O(n2);

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。