给定一个非负整数 numRows，生成杨辉三角的前 numRows 行 在杨辉三角中，每个数是它左上方和右上方的数的和。
示例: 输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
package com.loo;
import java.util.List; import java.util.ArrayList;
public class Triangle { public static void main(String[] args) { int num = 5; List<List<Integer>> list = getTriangle2(num); // getTriangle(num); for (int i=0;i<list.size();i++) { for (int j=0;j<list.get(i).size();j++) { System.out.print(list.get(i).get(j)); } System.out.println(); } }
// 递归 public static List<List<Integer>> getTriangle(int numRows) { List<List<Integer>> triangle = new ArrayList(); if (numRows==0) { return triangle; } if (numRows==1) { triangle.add(new ArrayList()); triangle.get(0).add(1); return triangle; } triangle = getTriangle(numRows - 1); List<Integer> row = new ArrayList(); row.add(1); for (int j=1;j<numRows-1;j++) { row.add(triangle.get(numRows-2).get(j-1) + triangle.get(numRows-2).get(j)); } row.add(1); triangle.add(row); return triangle; }
// 动态规划 public static List<List<Integer>> getTriangle2(int numRows) { List<List<Integer>> triangle = new ArrayList(); if (numRows==0) { return triangle; } triangle.add(new ArrayList()); triangle.get(0).add(1); for (int i=2;i<=numRows;i++) { List<Integer> row = new ArrayList(); List<Integer> prevRow = triangle.get(i-2); row.add(1); for (int j=1;j<i-1;j++) { row.add(prevRow.get(j-1) + prevRow.get(j)); } row.add(1); triangle.add(row); } return triangle; } }
