题目描述

给定一个非负整数 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<List<Integer>> 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<List<Integer>> generate(int numRows) {

        if (numRows == 0) {

            return Collections.emptyList();

        }

        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {

            List<Integer> sub = new ArrayList<>();

            for (int j = 0; j <= i; j++) {

                if (j == 0 || j == i) {

                    sub.add(1);

                } else {

                    List<Integer> upSub = res.get(i - 1);

                    sub.add(upSub.get(j - 1) + upSub.get(j));

                }

            }

            res.add(sub);

        }

        return res;

    }

}