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, 18ms
System.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);
}
}
