“This is the second day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

Title description:

Yang Hui Triangle – Yang Hui Triangle – Force buckle (LeetCode) (leetcode-cn.com)

Given a non-negative integer numRows, generate the former numRows of the “Yang Hui triangle”.

In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.

Example 1:

Input: numRows = 5 output: [[1], [1, 1], [1, 2, 1],,3,3,1 [1], [1,4,6,4,1]]Copy the code

Example 2:

Input: numRows = 1 Output: [[1]]Copy the code

Tip:

  • 1 <= numRows <= 30

Thought analysis

The principle of Yang Hui triangle is quite simple, this GIF is so easy to understand, when I learned this at school, it does not take long for everyone to make it.

Yang Hui triangle has the following properties:

  • The numbers in each row are symmetrical, with the first and last digits being 1, gradually increasing in the middle, and then gradually decreasing to 1.
  • Each number is equal to the sum of the left and right digits on the previous row.

Once we know these two properties, we have figured out the law of Yang Hui’s triangle, and the next step is to translate it into code.

AC code

class Solution {
    fun generate(numRows: Int): List<List<Int> > {val res = arrayListOf<List<Int> > ()for (i in 0 until numRows) {
            val row = arrayListOf<Int> ()// Note that the first and last digits are fixed to 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

    }
}
Copy the code

conclusion

Although this problem is simple, according to the normal thinking to write words really is not difficult, minutes to do.

But wandering around the solution of the time, but also found an old brother’s strange solution

Trick solution: Add the wrong bits one by one, 28ms/12.5MB – Yang Hui Triangle – Force button (LeetCode) (leetcode-cn.com)

He found a pattern and used a mathematical solution

At the same time there is the use of high – profile dynamic programming solutions

The most Accessible Dynamic Programming solution Yang Hui Triangle – Yang Hui Triangle – Force buckle (LeetCode) (leetcode-cn.com)

I have to say, the problem never ends, and before I read it, I was thinking, well, isn’t that how you solve it, what else can you do? I got hit in the face by the big guy.

reference

Yang Hui Triangle – Yang Hui Triangle – Force buckle (LeetCode) (leetcode-cn.com)