題目連結: Pascal's Triangle II

題目描述為: 給定一個整數 n，要我們以陣列形式返回巴斯卡三角形的第 n 層所有數值，其中頂端為第 0 層。
題目有補充說明希望我們只使用 O(k) 的額外記憶體空間，且 n 介於 [0,40]。

例子1: n= 3, output=[1,3,3,1]。
例子2: n=0, output=[1]。
例子3: n=1, output=[1,1]。

思路 1: 動態規劃法

設 f(n)為一陣列表示巴斯卡三角形第 n 層的所有數值，且我們規定每層從第 0 個數開始，則我們有: 第 n 層第 k 個數的值為組合數 。根據等式: ，因此我們要求 f(n)的值可以依次求 f(0),f(1),f(2)...直到 f(n)。此形式與 day23,day24 的解法一致。

• 複雜度評估
  設要求的層數為 N，每層有 N+1 個數字，我們需要從最頂層開始依序求出所有的數，時間複雜度為 O(N²)。
  此方法至多需要保存第 N 層的所有數值，空間複雜度為 O(N)。

參考程式碼

func getRow(rowIndex int) []int {
    ans := make([]int, 1, rowIndex+1)
	ans[0] = 1
	if rowIndex == 0 {
		return ans
	}

	for i := 0; i < rowIndex; i++ {
		ans = append(ans, 1)
		for j := len(ans) - 2; j > 0; j-- {
			ans[j] += ans[j-1]
		}
	}

	return ans
}

小結:

巴斯卡三角形尚有一個性質為左右對稱，若充分利用此性質可使計算量減半，而時間複雜度依然為 O(N²)。
我將解法加上簡單的測試，上傳程式碼到此。

補充 :

若使用 的方式來計算組合數，則會遇到諸多問題如: 溢位，重複計算，...等，且需要做乘除運算，採用解法 1 來處理此問題明顯較佳。