Today ready to do Yang Hui triangle, my wife came to learn to write code with me, look at me staring at the topic meditating, asked me what is Yang Hui triangle? What is the Yang Hui Triangle? Come on, subject!

Topic describes

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]] example 2:

Input: numRows = 1 Output: [[1]]

Tip:

1 <= numRows <= 30

Answer key

The GIF above vividly explains the concept of Yang Hui’s triangle, in which the top of the triangle starts at 1 and each number in each row below is the sum of the numbers to its upper left and right. Once we understand the concept, let’s look at it from a procedural point of view. If you store each row of data in an array, and you look at it carefully, you’ll see that each of these numbers is equal to the sum of the index bits of the previous row and the index bits of the previous row.

Dp [I][j] = DP [i-1][j] + DP [i-1][J-1]. Yang Hui triangle is also a typical dynamic programming problem. Next is the idea of how to achieve the problem. In fact, one of the things I’ve learned about dynamic programming problems is that you do typical problems first, don’t think about the boundaries, put the boundaries last, because it’s hard to think about all the details at once.

First, the entry is the number of rows, so we iterate over the number of rows, each time we get all the data for the current row.

// Define the return result
var res = [];
for(var i =0; i < numRows; i++){
    // Define the result of each row
    var dp = [];
    // todo
    // Get the result of each row. res.push(dp) }return res
Copy the code

The general logic of the code is written above, which is equivalent to a template. The key problem now is how to get the data for each row.

Next, I now need to get an array on each line, which is added as an element to the final result. Dp [I][j] = dp[i-1][j] + dp[i-1][J-1] = dp[i-1] = dp[i-1] = dp[i-1]

// Define the return result
var res = [];
for(var i =0; i < numRows; i++){
    // Define the result of each row
    var dp = [];
    // Get the result of each row
    for(var j = 0; j<=i; j++){ dp.push( res[i-1][j] +  res[i-1][j-1])
    }
    res.push(dp)
}
return res
Copy the code

In this case, I haven’t taken into account the boundary problem, which is I =0 and j=0. And that’s easy to solve, because anything outside of the hyperboundary, it’s just 0. And then there’s the boundary case, which is line 0, where you just get the result and you just add it in. So the final complete code is as follows:

/ * * *@param {number} numRows
 * @return {number[][]}* /
var generate = function(numRows) {
    var res = []
    for(var i = 0; i< numRows; i++){
        var dp = []
        if(i=== 0) {
            dp = [1]
            res.push(dp)
        } else {
            for(var j = 0; j<=i; j++){ dp.push((j === res[i-1].length ? 0: res[i-1][j]) + (j-1 <0? 0 : res[i-1][j-1]))
            }
            res.push(dp)
        }
    }
    return res
};
Copy the code

I saw the official problem solution, in fact, the same train of thought, I first contact Yang Hui triangle can be solved, calculate good, write down the heart course, continue to progress!

Complexity analysis

  • Time complexity: O(numRows2), easy to understand, the outermost loop numRows times, inside the cumulative is (1+ N)*n/2, so the complexity can be understood as N2
  • Space complexity: O(1), constant level variable occupancy

Title link: leetcode-cn.com/problems/pa…