118. Pascal's Triangle (Dynamic Programming) 20.3.20 Easy

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.


In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution: --------------------------------------------------------- Dynamic Programming
------------------------------------------------------------------- O(numRows^2) T (two for loops) and S (res)
class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if not numRows:
            return None
        res = [[1]*(i + 1) for i in range(numRows)]                   # As for any 2-D list result, 
                                                                      # we should find a way to initialize it first,
                                                                      # then, we can use res[i][j] to assign or assess 
                                                                      # the values in it very easy
        for i in range(2, len(res)):
            for j in range(1, len(res[i]) - 1):
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j]
        return res


Java Version:
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows <= 0) {
            return res;
        }
        List<Integer> currRow = new ArrayList<>();
        
        for (int i = 0; i < numRows; i ++) {
            currRow.add(0, 1);
            for (int j = 1; j < currRow.size() - 1; j ++) {
                currRow.set(j, currRow.get(j) + currRow.get(j + 1));
            }
            res.add(new ArrayList<>(currRow));
        }
        return res;
    }
}