k740 - 楊輝三角形
題目描述
題目要求輸出高度為 n 的楊輝三角形。楊輝三角形的每個數等於它左上方與右上方的和，邊緣的數為 1。
解題思路
此題可以使用動態規劃的方式解決。首先初始化 a[0][0] = 1。然後，根據楊輝三角形的特性，遞迴地計算每個元素的值：a[i+1][j] += a[i][j] 和 a[i+1][j+1] += a[i][j]。預先計算好楊輝三角形的前 21 行，然後根據輸入的 n，輸出前 n 行。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n^2)
程式碼
#include <iostream>
using namespace std;
int n,a[22][22];
int main(){
a[0][0]=1;
for(int i=0;i<=20;++i){
for(int j=0;j<=i;++j){
a[i+1][j]+=a[i][j];
a[i+1][j+1]+=a[i][j];
}
}
cin >> n;
for(int i=0;i<n;++i){
for(int j=0;j<=i;++j){
cout << a[i][j] << " ";
}
cout << "\n";
}
}