119. 杨辉三角 II

杨辉三角

• 定义和性质
• 解法一：递推
• 解法二：线性递推

参考：
1.https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang-hui-san-jiao-ii-by-leetcode-solutio-shuk/
2.https://leetcode-cn.com/problems/pascals-triangle-ii/solution/shou-hua-tu-jie-119yang-hui-san-jiao-ii-d09dc/

定义和性质

杨辉三角，是二项式系数在三角形中的一种几何排列。它是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。

杨辉三角具有以下性质：

1.每行数字左右对称，由$1$开始逐渐变大再变小，并最终回到$1$。

2.第$n$行（从0开始编号）的数字有$n+1$项，前n行共有 n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1)​个数。

3.第$n$行的第$m$个数（从$0$开始编号）可表示为可以被表示为组合数 $\mathcal{C}(n,m)$，记作 C n m \mathcal{C}_n^m Cnm​或 ( n m ) \binom{n}{m} (mn​)，即为从$n$个不同元素中取$m$个元素的组合数。我们可以用公式来表示它： C n m = n ! m ! ( n − m ) ! \mathcal{C}_n^m=\dfrac{n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​

4.每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第$n$行的第$i$个数等于第$n-1$行的第$i-1$个数和第$i$个数之和。这也是组合数的性质之一，即 C n i = C n − 1 i + C n − 1 i − 1 \mathcal{C}_n^i=\mathcal{C}_{n-1}^i+\mathcal{C}_{n-1}^{i-1} Cni​=Cn−1i​+Cn−1i−1​。

5. ( a + b ) n (a+b)^n (a+b)n的展开式（二项式展开）中的各项系数依次对应杨辉三角的第$n$行中的每一项。

注意：

1. ( a + b ) n = C ( 0 , n ) a n + C ( 1 , n ) a n − 1 b + . . . . + C ( k , n ) a n − k b k + . . . . . + C ( n , n ) b n (a+b)^n=C(0,n)a^n+C(1,n)a^{n-1}b+....+C(k,n)a^{n-k}b^k+.....+C(n,n)b^n (a+b)n=C(0,n)an+C(1,n)an−1b+....+C(k,n)an−kbk+.....+C(n,n)bn

2. A n m = n ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) ⏟ m 个 因 子 = n ! ( n − m ) ! \mathcal{A}_n^m=\underbrace{n(n-1)(n-2)...(n-m+1)}_{m个因子}=\dfrac{n!}{(n-m)!} Anm​=m个因子 n(n−1)(n−2)...(n−m+1)​​=(n−m)!n!​
   ​

解法一：递推

依据性质4，递推式 C n i = C n − 1 i + C n − 1 i − 1 \mathcal{C}_n^i=\mathcal{C}_{n-1}^i+\mathcal{C}_{n-1}^{i-1} Cni​=Cn−1i​+Cn−1i−1​表明，当前行第i项的计算只与上一行第i−1项及第i项有关。因此可以倒着计算当前行，这样计算到第i项时，第i-1项仍然是上一行的值。

class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> row = new ArrayList<Integer>();row.add(1);for(int i=1;i<=rowIndex;i++){row.add(0);for(int j=i;j>0;j--){row.set(j,row.get(j)+row.get(j-1));}}return row;}
}

复杂度分析：

时间复杂度： O ( rowIndex 2 ) O(\textit{rowIndex}^2) O(rowIndex2)。

空间复杂度：$O(1)$。不考虑返回值的空间占用。

解法二：线性递推

由组合数公式 C n m = n ! m ! ( n − m ) ! \mathcal{C}_n^m=\dfrac{n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​，可以得到同一行的相邻组合数的关系 C n m = C n m − 1 × n − m + 1 m \mathcal{C}_n^m= \mathcal{C}_n^{m-1} \times \dfrac{n-m+1}{m} Cnm​=Cnm−1​×mn−m+1​
由于 C n 0 = 1 \mathcal{C}_n^0=1 Cn0​=1，利用上述公式我们可以在线性时间计算出第n行的所有组合数。

class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> row = new ArrayList<Integer>();row.add(1);for(int i=1;i<=rowIndex;i++){row.add((int)((long)row.get(i-1)*(rowIndex-i+1)/i));}return row;}
}

复杂度分析：

时间复杂度：$O(\text{rowIndex})$。

空间复杂度：$O(1)$。不考虑返回值的空间占用。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！