Leetcode: 118. Pascal's Triangle (Dynamic Programming)

Pascal's Triangle - Exploring Patterns in Numbers

Introduction

One of the fascinating mathematical patterns that has intrigued mathematicians for centuries is Pascal's Triangle. Named after the French mathematician Blaise Pascal, this triangular arrangement of numbers holds numerous interesting properties and applications in various fields.

The Problem

The problem involves generating Pascal's Triangle with a given number of rows. Each row of the triangle starts and ends with 1, and the other elements are calculated by summing the two numbers directly above it in the previous row.

For example, the first few rows of Pascal's Triangle look like this:

                   1
                1     1
             1     2     1
          1     3     3     1
       1     4     6     4     1
    

Approach

To generate Pascal's Triangle, we can use a nested loop structure. We iterate through each row and within each row, we calculate the values based on the previous row. The first and last elements of each row are always 1, and the middle elements are calculated using the formula: value = previousRow[j-1] + previousRow[j].

Complexity Analysis

The time complexity of generating Pascal's Triangle is O(n^2), where n is the number of rows. This is because we need to calculate each element of each row using the values from the previous row. The space complexity is also O(n^2) as we store the entire triangle in a 2D matrix.

Example

Let's illustrate the generation of Pascal's Triangle with an example where we generate the first 5 rows:

        #include <iostream>
        #include <vector>

        class Solution {
        public:
            std::vector> generate(int num_rows) {
                std::vector> triangle;

                for (int row_num = 0; row_num < num_rows; row_num++) {
                    std::vector row(row_num + 1, 1);

                    for (int j = 1; j < row.size() - 1; j++) {
                        row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j];
                    }

                    triangle.push_back(row);
                }

                return triangle;
            }
        };

        int main() {
            Solution solution;
            int num_rows = 5;
            std::vector> result = solution.generate(num_rows);

            // Print the generated triangle
            for (const auto& row : result) {
                for (const auto& num : row) {
                    std::cout << num << " ";
                }
                std::cout << std::endl;
            }

            return 0;
        }
    

When we run the above code, it generates the following output:

        1
        1 1
        1 2 1
        1 3 3 1
        1 4 6 4 1
    

Conclusion

Pascal's Triangle is a captivating mathematical construct that exhibits numerous patterns and properties. It finds applications in combinatorics, probability theory, and other branches of mathematics. By understanding the approach to generate Pascal's Triangle, you can explore and appreciate the intriguing patterns hidden within this triangular array of numbers.

Feel free to experiment with different numbers of rows and explore the patterns that emerge from Pascal's Triangle!