LeetCode-118. 杨辉三角

╰+哭是因爲堅強的太久メ 2024-03-24 14:08 23阅读 0赞

#### 目录 ####

*   *  题目思路
     *  动态规划

题目来源  
[118. 杨辉三角][118.]

### 题目思路 ###

先把这个List<List< String >>转换成二维数组，从题目可以看出都依赖于上面的两个数  
![在这里插入图片描述][b9b9eb5703834bc89cf5cbeae946a1b3.png]

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

根据上面的题目思路，确定是二维数组，定义成dp\[i\]\[j\]

*  2.确定递推公式

可以看出dp\[2\]\[2\]依赖于左上方和上方  
递推公式:dp\[i\]\[j\] = dp\[i-1\]\[j-1\] + dp\[i-1\]\[j\]  
![在这里插入图片描述][b9b9eb5703834bc89cf5cbeae946a1b3.png]

*  3.dp数组如何初始化

初始化就有意思，我们需要把题目给的条件初始化吗？  
No  
我们只需要初始化dp\[i\]\[0\]就可以了，因为dp\[i\]\[i\]（斜线）也依赖于左上方和上方

for(int i = 0;i<dp.length;i++){
        
       dp[i][0] = 1;
    }

*  4.确定遍历顺序

根据递推公式dp\[i\]\[j\] = dp\[i-1\]\[j-1\] + dp\[i-1\]\[j\]推出，所以是从下到上，从左到右

*  5.举例推导dp数组

numRows = 5

![在这里插入图片描述][1e5e2ab6e8b34e1689291e4cb6cf00c6.png]  
代码实现

class Solution {
        
        public List<List<Integer>> generate(int numRows) {
        
            List<Integer> path = new ArrayList<>();
            List<List<Integer>> result = new ArrayList<>();
            int[][] dp = new int[numRows][numRows];
            dp[0][0] = 1;
            for(int i = 1;i<dp.length;i++){
        
                dp[i][0] = 1;
                for(int j = 1;j<dp[0].length;j++){
        
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }
            }
            for(int i = 0;i<dp.length;i++){
        
                for(int j = 0;j<=i;j++){
        
                    path.add(dp[i][j]);
                }
                result.add(new ArrayList(path));
                path.clear();
            }
            return  result;
        }
    }

![在这里插入图片描述][82015b02e332427b8a969fcafb97f7a2.png]

[118.]: https://leetcode.cn/problems/pascals-triangle/
[b9b9eb5703834bc89cf5cbeae946a1b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/1384f03ab90c41bcbe9ea61179bcb338.png
[1e5e2ab6e8b34e1689291e4cb6cf00c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/df8cb3d4dcee4b98bb566c325d07f036.png
[82015b02e332427b8a969fcafb97f7a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/cef581820dd04141b02f2ad52f64ff39.png