【题解】力扣119.杨辉三角Ⅱ

题目来源

119. 杨辉三角 II

思路

方法一

杨辉三角的性质：

1. 每行数字左右对齐，由1开始逐渐变大再变小，并最终回到1.
2. 第\(n\)行（从\(0\)开始编号）的数字有\(n+1\)项，前\(n\)行共有\(\frac{n(n+1)}{2}\)个数。
3. 第\(n\)行的第\(m\)个数（从\(0\)开始编号）可表示为可以被表示为组合数\(C(n,m)\)，记作\(C_{n}^{m}\)或 \(\binom{n}{m}\)，即为从n个不同元素中取m个元素的组合数。我们可以用公式来表示它：\(C_n^m = \frac{n!}{m!(n?m)!}\)
4. 每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第n行的第i个数等于第n-1行的第i-1个数和第i个数之和。即\(C_n^i=C_{n-1}^i+C_{n-1}^{i-1}\)。
5. \((a+b)^n\)的展开式（二项式展开）中的各项系数一次对应杨辉三角的第\(n\)行中的每一项。

递推：

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

优化

用滚动数组的思想，优化空间复杂度。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> cur = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }
}

进一步优化

动态规划+滚动数组优化，只用一个数组，从后往前（从右往左）更新

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;
        // 另一种写法：
        // Integer[] dp = new Integer[rowIndex+1];
        // Arrays.fill(dp,1);
        // for(int i = 2;i<dp.length;i++){
        //     for(int j = i-1;j>=0;j--){
        //         dp[j] = dp[j] + dp[j-1];
        //     }
        // }
        // List<Integer> res = Arrays.asList(dp);
        // return res;
    }
}

复杂度分析

1. 时间复杂度：\(O(rowIndex^2)\)。
2. 空间复杂度：\(O(1)\)。不考虑方绘制的空间占用。

方法二

线性递推。由组合数公式\(C_n^m = \frac{n!}{m!(n-m)!}\)，可以得到同一行的相邻组合数的关系

由于\(C_n^0 = 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(rowIndex)\)。
• 空间复杂度：\(O(1)\)。不考虑返回值的空间占用。

参考来源

1. 力扣官方题解：杨辉三角Ⅱ

【题解】力扣119.杨辉三角Ⅱ

原文：https://www.cnblogs.com/zzzzzy2k/p/14406524.html