题目描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5输出:[     [1],    [1,1],   [1,2,1],  [1,3,3,1], [1,4,6,4,1]]

思路

对任意的n>0有

f(1, n)=1，(n>0)

f(1, 2)=1，(n=2)

f(i,j) = f(i-1, j-1)+f(i, j-1)，i>2,j>2

代码实现

package Array;import java.util.ArrayList;import java.util.Collections;import java.util.List;/** * 118. Pascal's Triangle（杨辉三角） * 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。 */public class Solution118 {    public static void main(String[] args) {        Solution118 solution118 = new Solution118();        int numRows = 1;        List
    
     
      > res = solution118.generate(numRows);        System.out.println(res);    }    /**     * 对任意的n>0有     * f(1, n)=1，(n>0)     * f(1, 2)=1，(n=2)     * f(i,j) = f(i-1, j-1)+f(i, j-1)，i>2,j>2     *     * @param numRows     * @return     */    public List
      
       
        > generate(int numRows) {        if (numRows == 0) {            return Collections.emptyList();        }        List
        
         
          > res = new ArrayList<>(); for (int i = 0; i < numRows; i++) { List
          
            sub = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { sub.add(1); } else { List
           
             upSub = res.get(i - 1); sub.add(upSub.get(j - 1) + upSub.get(j)); } } res.add(sub); } return res; }}