数学经典 : 计算「杨辉三角」的和

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的119. 杨辉三角 II。

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

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

示例:

输入: 3

输出: [1,3,3,1]
复制代码

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

朴素 DP 解法

一个朴素的做法是按照给定信息进行模拟。

代码：

class Solution {
    public List<Integer> getRow(int idx) {
        int[][] f = new int[idx + 1][idx + 1];
        f[0][0] = 1;
        for (int i = 1; i < idx + 1; i++) {
            for (int j = 0; j < i + 1; j++) {
                f[i][j] = f[i - 1][j];
                if (j - 1 >= 0) f[i][j] += f[i - 1][j - 1];
                if (f[i][j] == 0) f[i][j] = 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < idx + 1; i++) ans.add(f[idx][i]);
        return ans;
    }
}
复制代码

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

滚动数组

滚动数组优化十分机械，直接将滚动的维度从 i 改造为 i % 2 或 i & 1 即可。

i & 1 相比于 i % 2 在不同架构的机器上，效率会更稳定些 ~

class Solution {
    public List<Integer> getRow(int idx) {
        int[][] f = new int[2][idx + 1];
        f[0][0] = 1;
        for (int i = 1; i < idx + 1; i++) {
            for (int j = 0; j < i + 1; j++) {
                f[i & 1][j] = f[(i - 1) & 1][j];
                if (j - 1 >= 0) f[i & 1][j] += f[(i - 1) & 1][j - 1];
                if (f[i & 1][j] == 0) f[i & 1][j] = 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < idx + 1; i++) ans.add(f[idx & 1][i]);
        return ans;
    }
}
复制代码

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

维度消除 DP 解法

只有第 i 行的更新只依赖于 i - 1 行，因此可以直接消除行的维度：

class Solution {
    public List<Integer> getRow(int idx) {
        int[] f = new int[idx + 1];
        f[0] = 1;
        for (int i = 1; i < idx + 1; i++) {
            for (int j = i; j >= 0; j--) {
                if (j - 1 >= 0) f[j] += f[j - 1];
                if (f[j] == 0) f[j] = 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < idx + 1; i++) ans.add(f[i]);
        return ans;
    }
}
复制代码