leetcode118. 楊輝三角

給定一個非負整數(shù) numRows，生成「楊輝三角」的前 numRows 行。

在「楊輝三角」中，每個數(shù)是它左上方和右上方的數(shù)的和。

示例 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

藍橋杯有個類似的題目，我曾寫過題解。

題目分析

楊輝三角是一個經(jīng)典的數(shù)學問題，每一行的第一個和最后一個數(shù)字都是1，其他位置的數(shù)字是它上方和左上方數(shù)字之和。這個問題可以通過動態(tài)規(guī)劃的方式來解決。

算法步驟

1. 初始化結果數(shù)組 res 和臨時數(shù)組 t。
2. 特殊處理第一行，將 1 加入 t，然后將 t 加入 res。
3. 如果 numRows 為1，直接返回 res。
4. 初始化二維數(shù)組 nums 用于記錄中間結果，大小為 40x40（根據(jù)題目需求設定）。
5. 使用雙重循環(huán)遍歷每一行，計算當前行的數(shù)值：
   • 對于每一行的第一個和最后一個數(shù)字，直接設置為1。
   • 對于其他位置的數(shù)字，計算方式為 nums[i-1][j-1] + nums[i-1][j]。
6. 將計算結果存入 res。

算法流程

具體代碼

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> res;vector<int> t;t.push_back(1);res.push_back(t);if(numRows==1) return res;int nums[40][40]={0};nums[1][1]=1;for(int i=2;i<=numRows;i++){vector<int> temp;temp.push_back(1);nums[i][1]=1;for(int j=2;j<=i-1;j++)  //i=4 {int sum=nums[i-1][j-1]+nums[i-1][j];temp.push_back(sum);nums[i][j]=sum;}temp.push_back(1);nums[i][i]=1;res.push_back(temp);}return res;}
};

算法分析

• 時間復雜度: O(numRows^2)，因為需要計算每一行的數(shù)值。
• 空間復雜度: O(numRows^2)，因為需要存儲每一行的數(shù)值。
• 易錯點: 在計算每一行的數(shù)值時，需要注意邊界條件，即每一行的第一個和最后一個數(shù)字都是1。

相似題目

題目	鏈接
118. 楊輝三角	https://leetcode.cn/problems/pascals-triangle/
119. 楊輝三角 II	https://leetcode.cn/problems/pascals-triangle-ii/
劍指 Offer 47. 禮物的最大價值	https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/