1. 杨辉三角：

                    是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。 --百度百科

2. 杨辉三角特点：

                               1. 每个数等于它上方两数之和               

                               2. 每行数字左右对称，由1开始逐渐变大

                               3. 第n行的数字有n项

                               4. 前n行共[(1+n)n]/2 个数

                               5. 第n行的m个数可表示为 C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数

3. 图像：

4.公式：

           行 i，列 j ，那么 [i][j] 的取值应为 [i-1]*[j-1] + [i-1][j]

           当i=0 或 i=j 时， [i][j]值为1

5. 多路递归第一版：

package com.nami.algorithm.study.day09;/*** beyond u self and trust u self.** @Author: lbc* @Date: 2023-09-20 14:32* @email: 594599620@qq.com* @Description: keep coding*/
public class PascalTriangle {public static int calculate(int i, int j) {if (i == j || j == 0) {return 1;}return calculate(i - 1, j - 1) + calculate(i - 1, j);}/*** 每行空白区域* @param n* @param i*/private static void printSpace(int n, int i) {// 参数2 与下面打印的 %-4d 的数字有关系，是他的一半int num = (n - 1 - i) * 2;for (int j = 0; j < num; j++) {System.out.print(" ");}}public static void print(int row) {for (int i = 0; i < row; i++) {printSpace(row, i);for (int j = 0; j <= i; j++) {
//                System.out.print(calculate(i, j) + " ");System.out.printf("%-4d", calculate(i, j));}System.out.println();}}public static void main(String[] args) {long start = System.currentTimeMillis();print(10);System.out.println(System.currentTimeMillis() -start + "ms");}}

 6. 当前版本可优化地方，同之前相同，用数组当缓存，存储之前计算得值。他得结果同之前计算得有关系；时间在层数多了之后，速度明显提升

package com.nami.algorithm.study.day09;/*** 二维数组记忆法* beyond u self and trust u self.** @Author: lbc* @Date: 2023-09-20 14:32* @email: 594599620@qq.com* @Description: keep coding*/
public class PascalTrianglePlus {public static int calculate(int[][] cache, int i, int j) {// 判断数组内是否有上一行得值if (cache[i][j] > 0) {return cache[i][j];}if (i == j || j == 0) {cache[i][j] = 1;return 1;}// 存入数组，方便下次使用cache[i][j] = calculate(cache, i - 1, j - 1) + calculate(cache, i - 1, j);return cache[i][j];}/*** 每行空白区域* @param n* @param i*/private static void printSpace(int n, int i) {// 参数2 与下面打印的 %-4d 的数字有关系，是他的一半int num = (n - 1 - i) * 2;for (int j = 0; j < num; j++) {System.out.print(" ");}}public static void print(int row) {// 使用二维数组记忆法// 也可以使用map，但是感觉没有数组简洁，map占用更大int[][] cache = new int[row][];for (int i = 0; i < row; i++) {cache[i] = new int[i + 1];printSpace(row, i);for (int j = 0; j <= i; j++) {
//                System.out.print(calculate(i, j) + " ");System.out.printf("%-4d", calculate(cache, i, j));}System.out.println();}}public static void main(String[] args) {long start = System.currentTimeMillis();print(50);// 当打印30层时候，二者速度：1700ms, 18msSystem.out.println(System.currentTimeMillis() -start + "ms");}}

7. 非递归方式解决，采用直接计算好每行的值

package com.nami.algorithm.study.day09;/*** 非递归方式* beyond u self and trust u self.** @Author: lbc* @Date: 2023-09-20 14:32* @email: 594599620@qq.com* @Description: keep coding*/
public class PascalTriangleUltra {public 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];}}private static void printSpace(int n, int i) {// 参数2 与下面打印的 %-4d 的数字有关系，是他的一半int num = (n - 1 - i) * 2;for (int j = 0; j < num; j++) {System.out.print(" ");}}public static void print(int row) {// 使用二维数组记忆法// 也可以使用map，但是感觉没有数组简洁，map占用更大int[] cache = new int[row];for (int i = 0; i < row; i++) {createRow(cache, i);printSpace(row, i);for (int j = 0; j <= i; j++) {
//                System.out.print(calculate(i, j) + " ");System.out.printf("%-4d", cache[j]);}System.out.println();}}public static void main(String[] args) {long start = System.currentTimeMillis();print(10);// 当打印40层时候 ， plus ,ultra 二者速度：21ms, 21ms 差不多System.out.println(System.currentTimeMillis() - start);}}