文章目录

• • • 一. 问题描述
    • • 示例 1
      • 示例 2
      • 提示
    • 二. 解决问题
    • • 主函数：
      • 法一：递归
      • • 1. 解题思路
        • 2. 解题代码
      • 法二：动态规划
      • • 1. 解题思路
        • 2. 解题代码
      • 法三：暴力破解
      • • 1. 解题思路
        • 2. 解题代码

一. 问题描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2

输入: numRows = 1
输出: [[1]]

提示

1 <= numRows <= 30

二. 解决问题

主函数：

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int num = sc.nextInt();for(List i : generate2(num)){System.out.println(i);}}

法一：递归

1. 解题思路

递归方法总而言之就是抓住三点：

• 找整个递归的终止条件
• 找返回值
• 一次递归需要如何操作

• 找整个递归的终止条件：
  • 递归至numRows = 0或者numRows = 1都可以终止。
• 找返回值：
  • 题目返回值为List ，也就是每一行遍历完一个list，之后把list附加到总的list之后就OK了。
• 一次递归需要如何操作：
  
  • 看一看第二行 -> 第三行是如何操作的：
    • 第一位和最后一位都是1，中间的数字再进行计算。
    • row.add(dg.get(numRows - 2).get(j - 1) + dg.get(numRows - 2).get(j))

2. 解题代码

 public static List> generate(int numRows) {List> dg = new ArrayList<>();if(numRows == 0)return dg;if(numRows == 1){dg.add(new ArrayList<>());dg.get(0).add(1);return dg;}//dg得接收这个返回值，要不然，递归进去东西，根本没有更新dg = generate(numRows - 1 );List row = new ArrayList<>();row.add(1);//假设numRows = 3，那么它那一行就应该有3个元素，又是用list存储的，所以j < numRows - 1。for(int j = 1; j < numRows - 1; j++){//-2的原因是因为list是从0开始存储的，而要的数据为上一层的数据row.add(dg.get(numRows - 2).get(j - 1) + dg.get(numRows - 2).get(j));}row.add(1);dg.add(row);return dg;}

法二：动态规划

1. 解题思路

• 和法一比较类似，只是将递归换成了迭代。引入了Prerow，保存上一个list中的数据。

2. 解题代码

 public static List> generate1(int numRows){List> dp = new ArrayList<>();if(numRows == 0)return dp;//考虑用迭代来操作dp.add(new ArrayList<>());dp.get(0).add(1);//i 为行数for(int i = 2; i <= numRows; i++){List row = new ArrayList<>();//i表示的是行数，而dp是从0开始存的，上一个为dp[0]，也就是第一行List Prerow = dp.get(i - 2);row.add(1);//一行当中第一个元素为1，最后一个元素也为1，所以为jrow.add(Prerow.get(j - 1) + Prerow.get(j));}row.add(1);//一行结束了，要并入总的list里面dp.add(row);}return dp;}

法三：暴力破解

1. 解题思路

• 一行一行遍历，该加的数字相加。

2. 解题代码

    public static List> generate2(int numRows) {List> res = new ArrayList<>();for(int i = 0;iList ans = new ArrayList<>();for(int j = 0;j<=i;j++){if(j == 0 || j == i){ans.add(1);}else{ans.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));}}res.add(ans);}return res;}

参考：https://leetcode.cn/problems/pascals-triangle/solution/javadi-gui-dong-tai-gui-hua-by-jeromememory/