# 输出杨辉三角

可以看到上图就是杨辉三角，它的两边都是 1 而下面的值就是正上方左右两个数字的和。

比如说 2 它的正上方就是 1 和 1 所以相加就是 2。以此类推

分析

把它斜着看

代码：

	public class Yanghuisanjiao
	{
	private static int element(int i, int j)
	{
	if(j == 0 \|\| i == j)
	{
	return 1;
	}
	return element(i - 1, j - 1) + element(i - 1, j);
	}

	private static void printSpace(int n, int i)
	{
	int num = (n - 1 - i) * 2;
	for(int j = 0; j < num; j++)
	{
	System.out.print(" ");
	}
	}

	public static void print(int n)
	{
	for(int i = 0; i < n; i++)
	{
	printSpace(n, i);
	for(int j = 0; j <= i; j++)
	{
	System.out.printf("%-4d", element(i, j));
	}
	System.out.println();
	}
	}

	public static void main(String[] args)
	{
	print(5);
	}
	}

打印结果：

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

# 记忆法

使用记忆法来消除重复计算的情况

	public class Yanghuisanjiao
	{
	private static int element(int i, int j)
	{
	if(j == 0 \|\| i == j)
	{
	return 1;
	}
	return element(i - 1, j - 1) + element(i - 1, j);
	}

	private static void printSpace(int n, int i)
	{
	int num = (n - 1 - i) * 2;
	for(int j = 0; j < num; j++)
	{
	System.out.print(" ");
	}
	}

	private static int element1(int triangle[][], int i, int j)
	{
	if(triangle[i][j] > 0)
	{
	return triangle[i][j];
	}

	if(j == 0 \|\| i == j)
	{
	triangle[i][j] = 1;
	return 1;
	}
	triangle[i][j] = element1(triangle, i - 1, j - 1) + element1(triangle, i - 1, j);
	return triangle[i][j];
	}



	public static void print(int n)
	{
	for(int i = 0; i < n; i++)
	{
	printSpace(n, i);
	for(int j = 0; j <= i; j++)
	{
	System.out.printf("%-4d", element(i, j));
	}
	System.out.println();
	}
	}

	public static void print1(int n)
	{
	int triangle[][] = new int[n][];
	for(int i = 0; i < n; i++)
	{
	triangle[i] = new int[i + 1];
	printSpace(n, i);
	for(int j = 0; j <= i; j++)
	{
	System.out.printf("%-4d", element1(triangle, i, j));
	}
	System.out.println();
	}
	}

	public static void main(String[] args)
	{
	print1(5);
	}
	}

打印结果：

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

上面的记忆法使用了二维数组占用了很大的空间，下面对记忆法进行空间优化

	private static void printSpace(int n, int i)
	{
	int num = (n - 1 - i) * 2;
	for(int j = 0; j < num; j++)
	{
	System.out.print(" ");
	}
	}
	private static void createRow(int row[], int i)
	{
	if(i == 0)
	{
	row[0] = 1;
	return;
	}
	for (int j = i; j > 0; j--)
	{
	row[j] = row[j] + row[j - 1];
	}
	}

	public static void print2(int n)
	{
	int row[] = new int[n];
	for (int i = 0; i < n; i++)
	{
	createRow(row, i);
	printSpace(n, i);
	for (int j = 0; j <= i; j++)
	{
	System.out.printf("%-4d", row[j]);
	}
	System.out.println();
	}
	}

	public static void main(String[] args)
	{
	print2(6);
	}

打印结果：

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

注意：还可以通过每一行的前一项计算出下一项，不必借助上一行，这与杨辉三角的另一个特性有关