Ricky.L的随笔
0%

LeetCode.118.杨辉三角（简单）

发表于 更新于 分类于 Disqus：

题目

LeetCode.118.杨辉三角（简单）

给定一个非负整数 _numRows，_生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

题解

递推公式题目已经给出，讨论一下边界情况，把问题具体定义就好了。

问题公式化

三角形每行用List存储，所有行也用List存储。
设dp[r][c]是杨辉三角第r行第c列的数。
把三角形左侧对齐可以观察到：
左上方的数就是dp[r - 1][c - 1]；
右上方的数就是dp[r - 1][c]；

状态转移方程

dp[r][c] = dp[r - 1][c - 1] + dp[r - 1][c]

边界处理

r = 0时，没有上方，但其实知道第一行是1，只有1个元素，直接添加到结果集就行了。
r > 0后：
c = 0 处于第一列时，没有左上方，左上方当作0，只累加右上方，dp[r][0] = dp[r - 1][c]。
c = r 处于最后一列时，没有右上方，右上方当作0，只累加左上方，dp[r][r] = dp[r - 1][r - 1]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()
        triangle.add(listOf(1))
        for (r in 1 until numRows) {
            val rows = mutableListOf<Int>()
            for (c in 0..r) {
                when {
                    // 第一列，只能加右上方
                    c == 0 -> rows.add(triangle[r - 1][0])
                    // 最后一列，只能加左上方
                    c == r -> rows.add(triangle[r - 1][r - 1])
                    // 中间列，左上方+右上方
                    else -> rows.add(triangle[r - 1][c - 1] + triangle[r - 1][c])
                }
            }
            triangle.add(rows)
        }
        return triangle
    }
}