LeetCode.118 杨辉三角

题目描述：

杨辉三角 - 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)

给定一个非负整数 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 <= numRows <= 30

思路分析

杨辉三角的原理还是蛮简单的，这个动图这么通俗易懂，上学时代学这个的时候，也不用多久大家都能做出来。

杨辉三角具有以下性质：

• 每行数字左右对称，第一位和最后一位都是1，中间是逐渐变大，然后再逐渐变小到1。
• 每个数字等于上一行的左右两个数字之和(上面动图很简单就看出来了)

当我们知晓这两个性质之后，我们就已经弄清楚了杨辉三角的规律了，接下来就是转化为代码就好了。

AC代码

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val res = arrayListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = arrayListOf<Int>()
            //注意第一位和最后一位固定为1
            for (j in 0 until i + 1) {
                if (j == 0 || j == i) {
                    row.add(1)
                } else {
                    row.add(res[i - 1][j - 1] + res[i - 1][j])
                }
            }
            res.add(row)
        }
        return res

    }
}

总结

这题虽然是简单题，按照正常思维去写的话确实也不难，分分钟做出来。

但是逛题解的时候，还发现了一个老哥的清奇的解法

取巧解法：错一位再逐个相加，28ms/12.5MB - 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)

他发现了规律，利用了数学的解法

同时还有利用高大上的动态规划的解法的

最通俗易懂的动态规划解决杨辉三角 - 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)

不得不说，解题永无止境，没看之前，我都在想，这题不就这么解吗，还能玩出什么花来？结果果然被大佬打脸。

参考

杨辉三角 - 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)